Submission #527994


Source Code Expand

/*{{{*/
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <functional>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
typedef int8_t sbyte;
typedef uint8_t byte;
typedef uint16_t ushort;
typedef uint32_t uint;
typedef int64_t i64;
typedef uint64_t u64;
template<class T> static inline T ABS(T x) {return x < 0 ? -x : x;}
template<class T> static inline void MAZ(T &a, const T &b) {if(a < b) a = b;}
template<class T> static inline void MIZ(T &a, const T &b) {if(b < a) a = b;}
/*}}}*/

static const auto NMAX = 1000;
static inline int PAIR(int i, int j) {return i << 10 | j;}
static inline int FRST(int p) {return p >> 10;}
static inline int SCND(int p) {return p & 1023;}

static const int dir[4][2] = {{-1, 0}, {0, -1}, {0, +1}, {+1, 0}};
static inline int neg(int k) {return k ^ 3;}

static int N;
static char M[NMAX][NMAX + 1];

static bool W[NMAX][NMAX][5];
static int C[NMAX][NMAX];

static inline bool inmap(int i, int j) {
	return 0 <= i && i < N && 0 <= j && j < N;
}

static bool solve() {
	if(M[N - 1][N - 1] == '.') return false;
	vector<int> s;
	for(auto k = 0; k < 4; k++) {
		W[N - 1][N - 1][k] = true;
		s.push_back(PAIR(N - 1, N - 1) << 3 | k);
	}
	while(!s.empty()) {
		auto k = s.back() & 7;
		auto i = FRST(s.back() >> 3);
		auto j = SCND(s.back() >> 3);
		s.pop_back();
		if(k == 4) {
			for(k = 0; k < 4; k++) {
				auto ii = i + dir[k][0];
				auto jj = j + dir[k][1];
				if(!inmap(ii, jj)) continue;
				for(auto kk = 0; kk < 4; kk++) {
					if(M[i][j] == '.' && kk == neg(k)) continue;
					if(W[ii][jj][kk]) continue;
					W[ii][jj][kk] = true;
					s.push_back(PAIR(ii, jj) << 3 | kk);
				}
			}
		} else if(++C[i][j] == 4) {
			W[i][j][4] = true;
			s.push_back(PAIR(i, j) << 3 | 4);
		}
	}
	return W[0][0][4];
}

int main() {
	scanf("%d", &N);
	for(auto i = 0; i < N; i++) scanf("%s", M[i]);
	puts(solve() ? "YES" : "NO");
	return 0;
}

Submission Info

Submission Time
Task I - Obstruction
User arosusti
Language C++11 (GCC 4.8.1)
Score 100
Code Size 2299 Byte
Status AC
Exec Time 209 ms
Memory 14344 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:88:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
./Main.cpp:89:47: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(auto i = 0; i < N; i++) scanf("%s", M[i]);
                                               ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 65
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All manual_j1.txt, manual_j10.txt, manual_j11.txt, manual_j12.txt, manual_j13.txt, manual_j14.txt, manual_j15.txt, manual_j16.txt, manual_j17.txt, manual_j18.txt, manual_j19.txt, manual_j2.txt, manual_j20.txt, manual_j21.txt, manual_j22.txt, manual_j23.txt, manual_j24.txt, manual_j25.txt, manual_j26.txt, manual_j27.txt, manual_j28.txt, manual_j29.txt, manual_j3.txt, manual_j30.txt, manual_j31.txt, manual_j32.txt, manual_j33.txt, manual_j34.txt, manual_j4.txt, manual_j5.txt, manual_j6.txt, manual_j7.txt, manual_j8.txt, manual_j9.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, scale_01.txt, scale_02.txt, scale_03.txt, scale_04.txt, scale_05.txt, scale_small_01.txt, scale_small_02.txt, scale_small_03.txt, scale_small_04.txt, scale_small_05.txt, scale_small_06.txt
Case Name Status Exec Time Memory
manual_j1.txt AC 51 ms 1096 KB
manual_j10.txt AC 28 ms 1104 KB
manual_j11.txt AC 27 ms 1048 KB
manual_j12.txt AC 26 ms 1048 KB
manual_j13.txt AC 26 ms 984 KB
manual_j14.txt AC 27 ms 1052 KB
manual_j15.txt AC 27 ms 1100 KB
manual_j16.txt AC 29 ms 1432 KB
manual_j17.txt AC 28 ms 1304 KB
manual_j18.txt AC 28 ms 1172 KB
manual_j19.txt AC 27 ms 1052 KB
manual_j2.txt AC 27 ms 1176 KB
manual_j20.txt AC 27 ms 1040 KB
manual_j21.txt AC 27 ms 1100 KB
manual_j22.txt AC 30 ms 1056 KB
manual_j23.txt AC 28 ms 1148 KB
manual_j24.txt AC 26 ms 920 KB
manual_j25.txt AC 28 ms 1044 KB
manual_j26.txt AC 27 ms 1048 KB
manual_j27.txt AC 27 ms 1048 KB
manual_j28.txt AC 30 ms 1052 KB
manual_j29.txt AC 27 ms 1052 KB
manual_j3.txt AC 27 ms 1108 KB
manual_j30.txt AC 27 ms 1044 KB
manual_j31.txt AC 25 ms 1048 KB
manual_j32.txt AC 27 ms 1052 KB
manual_j33.txt AC 28 ms 1044 KB
manual_j34.txt AC 29 ms 1100 KB
manual_j4.txt AC 27 ms 1176 KB
manual_j5.txt AC 27 ms 1216 KB
manual_j6.txt AC 28 ms 1176 KB
manual_j7.txt AC 28 ms 1172 KB
manual_j8.txt AC 28 ms 1044 KB
manual_j9.txt AC 27 ms 1048 KB
random_01.txt AC 31 ms 2000 KB
random_02.txt AC 28 ms 1232 KB
random_03.txt AC 48 ms 1356 KB
random_04.txt AC 29 ms 1428 KB
random_05.txt AC 28 ms 1496 KB
random_06.txt AC 30 ms 1560 KB
random_07.txt AC 31 ms 1688 KB
random_08.txt AC 31 ms 1812 KB
random_09.txt AC 32 ms 1940 KB
random_10.txt AC 209 ms 12552 KB
random_11.txt AC 32 ms 1940 KB
random_12.txt AC 39 ms 3136 KB
random_13.txt AC 49 ms 4244 KB
random_14.txt AC 62 ms 5448 KB
random_15.txt AC 78 ms 6668 KB
random_16.txt AC 97 ms 7812 KB
random_17.txt AC 121 ms 9096 KB
random_18.txt AC 146 ms 10500 KB
random_19.txt AC 173 ms 11912 KB
random_20.txt AC 205 ms 13308 KB
sample_01.txt AC 27 ms 1044 KB
sample_02.txt AC 27 ms 1048 KB
sample_03.txt AC 27 ms 924 KB
scale_01.txt AC 165 ms 11532 KB
scale_02.txt AC 182 ms 14344 KB
scale_03.txt AC 78 ms 10508 KB
scale_04.txt AC 163 ms 10772 KB
scale_05.txt AC 86 ms 8004 KB
scale_small_01.txt AC 43 ms 3736 KB
scale_small_02.txt AC 46 ms 3984 KB
scale_small_03.txt AC 46 ms 3992 KB
scale_small_04.txt AC 32 ms 2836 KB
scale_small_05.txt AC 44 ms 3992 KB
scale_small_06.txt AC 49 ms 4744 KB