Contest Duration: ~ (local time) (120 minutes) Back to Home

Submission #219383

Source Code Expand

Copy
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <complex>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>

#define REP(i,x) for(int i=0 ; i<(int)(x) ; i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;

int N;
vector<string> field;

int memo[1000][1000][2];

const int dy[4] = {0,1,0,-1};
const int dx[4] = {1,0,-1,0};

bool valid(int x, int y){
return x>=0 && x<N && y>=0 && y<N;
}

bool rec(int x,int y){
if(y==N)return true;

if(x>0){
if(answer[y][x-1]=='#' && memo[x][y][0] == -1)return false;
if(answer[y][x-1]=='.' && memo[x][y][0] == -1)return false;
}

if(x==N)return rec(0, y+1);

for(int b=0 ; b<(1<<4) ; b++){
char draw[4];
int cnt = 0;
REP(i,4){
draw[i] = (b>>i&1) ? '#' : '.';
int ny = y+dy[i];
int nx = x+dx[i];
if(valid(nx,ny)){
cnt += (b>>i&1);
}
}

if(field[y][x]=='.' && cnt%2==1)continue;
if(field[y][x]=='#' && cnt%2==0)continue;

bool ok = true;
REP(i,4){
int ny = y+dy[i];
int nx = x+dx[i];
if(valid(nx,ny)){
cnt += (b>>i&1);
}
}
if(ok){
bool changed[4];
memset(changed, false, sizeof(changed));
REP(i,4){
int ny = y+dy[i];
int nx = x+dx[i];
if(valid(nx,ny)){
changed[i] = true;
}
}
}
if(rec(x+1,y)==1)return true;
REP(i,4){
int ny = y+dy[i];
int nx = x+dx[i];
if(valid(nx,ny) && changed[i]){
}
}
}
}
if(x>0){
}
return false;

}

int main(){
cin >> N;
field.resize(N);
REP(i,N)cin >> field[i];

memset(memo, 0, sizeof(memo));
rec(0,0);

return 0;
}

#### Submission Info

Submission Time 2014-08-23 22:16:48+0900 C - 天下一王国の歴史 nel215 C++ (G++ 4.6.4) 0 2733 Byte WA 458 ms 98416 KB

#### Judge Result

Set Name Score / Max Score Test Cases
small 0 / 25 0randomMasu1001.txt, 0randomMasu2001.txt, 0randomMasu2002.txt, 0randomMasu2003.txt, 0randomMasu2004.txt, 0randomMasu3001.txt, 0randomMasu3002.txt, 0randomMasu3003.txt, 0randomMasu3004.txt, 0randomMasu3005.txt, 0randomMasu3006.txt, 0randomMasu3008.txt, 0randomMasu3010.txt, 0randomMasu3011.txt, 0randomMasu3012.txt, 0randomMasu3013.txt, 0randomMasu3014.txt, 0randomMasu3015.txt, 0randomMasu3016.txt, 0randomMasu3017.txt, 0randomMasu3018.txt, 0randomMasu3019.txt, 0sample1.txt
medium 0 / 30 0randomMasu1001.txt, 0randomMasu2001.txt, 0randomMasu2002.txt, 0randomMasu2003.txt, 0randomMasu2004.txt, 0randomMasu3001.txt, 0randomMasu3002.txt, 0randomMasu3003.txt, 0randomMasu3004.txt, 0randomMasu3005.txt, 0randomMasu3006.txt, 0randomMasu3008.txt, 0randomMasu3010.txt, 0randomMasu3011.txt, 0randomMasu3012.txt, 0randomMasu3013.txt, 0randomMasu3014.txt, 0randomMasu3015.txt, 0randomMasu3016.txt, 0randomMasu3017.txt, 0randomMasu3018.txt, 0randomMasu3019.txt, 0sample1.txt, 1_manual1.txt, 1_manual2.txt, 1_manual3.txt, 1randomMasu004.txt, 1randomMasu005.txt, 1randomMasu006.txt, 1randomMasu007.txt, 1randomMasu008.txt, 1randomMasu009.txt, 1randomMasu4001.txt, 1randomMasu4002.txt, 1randomMasu4003.txt, 1randomMasu4004.txt, 1randomMasu4005.txt, 1randomMasu5001.txt, 1randomMasu5002.txt, 1randomMasu5003.txt, 1randomMasu5004.txt, 1randomMasu5005.txt, 1randomMasu6001.txt, 1randomMasu6002.txt, 1randomMasu6003.txt, 1randomMasu6004.txt, 1randomMasu6005.txt, 1randomMasu6006.txt, 1randomMasu7001.txt, 1randomMasu7002.txt, 1randomMasu7003.txt, 1randomMasu7004.txt, 1randomMasu7005.txt, 1randomMasu7006.txt, 1randomMasu7007.txt, 1randomMasu8001.txt, 1randomMasu8002.txt, 1randomMasu8003.txt, 1randomMasu8004.txt, 1randomMasu8005.txt, 1randomMasu8006.txt, 1randomMasu8007.txt, 1randomMasu8008.txt, 1randomMasu9001.txt, 1randomMasu9002.txt, 1randomMasu9003.txt, 1randomMasu9004.txt, 1randomMasu9005.txt, 1randomMasu9006.txt, 1randomMasu9007.txt, 1randomMasu9008.txt, 1sample2.txt
All 0 / 25 0randomMasu1001.txt, 0randomMasu2001.txt, 0randomMasu2002.txt, 0randomMasu2003.txt, 0randomMasu2004.txt, 0randomMasu3001.txt, 0randomMasu3002.txt, 0randomMasu3003.txt, 0randomMasu3004.txt, 0randomMasu3005.txt, 0randomMasu3006.txt, 0randomMasu3008.txt, 0randomMasu3010.txt, 0randomMasu3011.txt, 0randomMasu3012.txt, 0randomMasu3013.txt, 0randomMasu3014.txt, 0randomMasu3015.txt, 0randomMasu3016.txt, 0randomMasu3017.txt, 0randomMasu3018.txt, 0randomMasu3019.txt, 0sample1.txt, 1_manual1.txt, 1_manual2.txt, 1_manual3.txt, 1randomMasu004.txt, 1randomMasu005.txt, 1randomMasu006.txt, 1randomMasu007.txt, 1randomMasu008.txt, 1randomMasu009.txt, 1randomMasu4001.txt, 1randomMasu4002.txt, 1randomMasu4003.txt, 1randomMasu4004.txt, 1randomMasu4005.txt, 1randomMasu5001.txt, 1randomMasu5002.txt, 1randomMasu5003.txt, 1randomMasu5004.txt, 1randomMasu5005.txt, 1randomMasu6001.txt, 1randomMasu6002.txt, 1randomMasu6003.txt, 1randomMasu6004.txt, 1randomMasu6005.txt, 1randomMasu6006.txt, 1randomMasu7001.txt, 1randomMasu7002.txt, 1randomMasu7003.txt, 1randomMasu7004.txt, 1randomMasu7005.txt, 1randomMasu7006.txt, 1randomMasu7007.txt, 1randomMasu8001.txt, 1randomMasu8002.txt, 1randomMasu8003.txt, 1randomMasu8004.txt, 1randomMasu8005.txt, 1randomMasu8006.txt, 1randomMasu8007.txt, 1randomMasu8008.txt, 1randomMasu9001.txt, 1randomMasu9002.txt, 1randomMasu9003.txt, 1randomMasu9004.txt, 1randomMasu9005.txt, 1randomMasu9006.txt, 1randomMasu9007.txt, 1randomMasu9008.txt, 1sample2.txt, 2_manual1.txt, 2_manual10.txt, 2_manual2.txt, 2_manual3.txt, 2_manual4.txt, 2_manual5.txt, 2_manual6.txt, 2_manual7.txt, 2_manual8.txt, 2_manual9.txt, 2randomMasu010.txt, 2randomMasu011.txt, 2randomMasu012.txt, 2randomMasu013.txt, 2randomMasu014.txt, 2randomMasu015.txt, 2randomMasu016.txt, 2randomMasu017.txt, 2randomMasu018.txt, 2randomMasu019.txt, 2randomMasu100.txt, 2randomMasu101.txt, 2randomMasu102.txt, 2randomMasu103.txt, 2randomMasu104.txt, 2randomMasu105.txt, 2randomMasu106.txt, 2randomMasu107.txt, 2randomMasu108.txt, 2randomMasu109.txt, 2randomMasu300.txt, 2randomMasu301.txt, 2randomMasu302.txt, 2randomMasu303.txt, 2randomMasu304.txt, 2randomMasu305.txt, 2randomMasu306.txt, 2randomMasu307.txt, 2randomMasu308.txt, 2randomMasu309.txt, 2randomMasu500.txt, 2randomMasu501.txt, 2randomMasu502.txt, 2randomMasu503.txt, 2randomMasu504.txt, 2randomMasu505.txt, 2randomMasu506.txt, 2randomMasu507.txt, 2randomMasu508.txt, 2randomMasu509.txt, 2randomMasu740.txt, 2randomMasu741.txt, 2randomMasu742.txt, 2randomMasu743.txt, 2randomMasu744.txt, 2randomMasu745.txt, 2randomMasu746.txt, 2randomMasu747.txt, 2randomMasu748.txt, 2randomMasu749.txt, 2randomMasu750.txt, 2randomMasu750b.txt, 2sample3.txt
Case Name Status Exec Time Memory
0randomMasu1001.txt 37 ms 8612 KB
0randomMasu2001.txt 35 ms 8560 KB
0randomMasu2002.txt 36 ms 8608 KB
0randomMasu2003.txt 34 ms 8600 KB
0randomMasu2004.txt 35 ms 8608 KB
0randomMasu3001.txt 35 ms 8608 KB
0randomMasu3002.txt 37 ms 8540 KB
0randomMasu3003.txt 37 ms 8616 KB
0randomMasu3004.txt 34 ms 8612 KB
0randomMasu3005.txt 34 ms 8732 KB
0randomMasu3006.txt 36 ms 8560 KB
0randomMasu3008.txt 37 ms 8544 KB
0randomMasu3010.txt 34 ms 8616 KB
0randomMasu3011.txt 35 ms 8612 KB
0randomMasu3012.txt 36 ms 8612 KB
0randomMasu3013.txt 37 ms 8600 KB
0randomMasu3014.txt 38 ms 8544 KB
0randomMasu3015.txt 36 ms 8564 KB
0randomMasu3016.txt 38 ms 8608 KB
0randomMasu3017.txt 40 ms 8616 KB
0randomMasu3018.txt 35 ms 8612 KB
0randomMasu3019.txt 37 ms 8564 KB
0sample1.txt 37 ms 8620 KB
1_manual1.txt 40 ms 8608 KB
1_manual2.txt 37 ms 8600 KB
1_manual3.txt 34 ms 8612 KB
1randomMasu004.txt 36 ms 8612 KB
1randomMasu005.txt 33 ms 8564 KB
1randomMasu006.txt 37 ms 8608 KB
1randomMasu007.txt 38 ms 8600 KB
1randomMasu008.txt 39 ms 8612 KB
1randomMasu009.txt 37 ms 8616 KB
1randomMasu4001.txt 41 ms 8608 KB
1randomMasu4002.txt 36 ms 8612 KB
1randomMasu4003.txt 36 ms 8608 KB
1randomMasu4004.txt 36 ms 8544 KB
1randomMasu4005.txt 36 ms 8616 KB
1randomMasu5001.txt 34 ms 8544 KB
1randomMasu5002.txt 37 ms 8620 KB
1randomMasu5003.txt 36 ms 8608 KB
1randomMasu5004.txt 35 ms 8608 KB
1randomMasu5005.txt 33 ms 8536 KB
1randomMasu6001.txt 36 ms 8604 KB
1randomMasu6002.txt 36 ms 8612 KB
1randomMasu6003.txt 36 ms 8620 KB
1randomMasu6004.txt 37 ms 8604 KB
1randomMasu6005.txt 34 ms 8616 KB
1randomMasu6006.txt 37 ms 8612 KB
1randomMasu7001.txt 40 ms 8592 KB
1randomMasu7002.txt 36 ms 8544 KB
1randomMasu7003.txt 36 ms 8556 KB
1randomMasu7004.txt 34 ms 8608 KB
1randomMasu7005.txt 35 ms 8552 KB
1randomMasu7006.txt 35 ms 8564 KB
1randomMasu7007.txt 37 ms 8616 KB
1randomMasu8001.txt 35 ms 8564 KB
1randomMasu8002.txt 36 ms 8616 KB
1randomMasu8003.txt 36 ms 8608 KB
1randomMasu8004.txt 36 ms 8736 KB
1randomMasu8005.txt 37 ms 8616 KB
1randomMasu8006.txt 36 ms 8612 KB
1randomMasu8007.txt 36 ms 8540 KB
1randomMasu8008.txt 36 ms 8612 KB
1randomMasu9001.txt 35 ms 8612 KB
1randomMasu9002.txt 35 ms 8624 KB
1randomMasu9003.txt 35 ms 8564 KB
1randomMasu9004.txt 36 ms 8616 KB
1randomMasu9005.txt 37 ms 8612 KB
1randomMasu9006.txt 36 ms 8636 KB
1randomMasu9007.txt 35 ms 8612 KB
1randomMasu9008.txt 35 ms 8736 KB
1sample2.txt 36 ms 8616 KB
2_manual1.txt 282 ms 98340 KB
2_manual10.txt 35 ms 8616 KB
2_manual2.txt 284 ms 98416 KB
2_manual3.txt 439 ms 98340 KB
2_manual4.txt 458 ms 98344 KB
2_manual5.txt 65 ms 18460 KB
2_manual6.txt 82 ms 18464 KB
2_manual7.txt 80 ms 18592 KB
2_manual8.txt 36 ms 8660 KB
2_manual9.txt 37 ms 8604 KB
2randomMasu010.txt 36 ms 8600 KB
2randomMasu011.txt 37 ms 8620 KB
2randomMasu012.txt 34 ms 8744 KB
2randomMasu013.txt 36 ms 8620 KB
2randomMasu014.txt 35 ms 8616 KB
2randomMasu015.txt 34 ms 8616 KB
2randomMasu016.txt 37 ms 8544 KB
2randomMasu017.txt 38 ms 8612 KB
2randomMasu018.txt 38 ms 8608 KB
2randomMasu019.txt 35 ms 8736 KB
2randomMasu100.txt 42 ms 10140 KB
2randomMasu101.txt 44 ms 10144 KB
2randomMasu102.txt 43 ms 10272 KB
2randomMasu103.txt 42 ms 10264 KB
2randomMasu104.txt 44 ms 10384 KB
2randomMasu105.txt 45 ms 10268 KB
2randomMasu106.txt 43 ms 10416 KB
2randomMasu107.txt 46 ms 10328 KB
2randomMasu108.txt 45 ms 10356 KB
2randomMasu109.txt 45 ms 10484 KB
2randomMasu300.txt 103 ms 22948 KB
2randomMasu301.txt 102 ms 23064 KB
2randomMasu302.txt 100 ms 23140 KB
2randomMasu303.txt 103 ms 23208 KB
2randomMasu304.txt 104 ms 23328 KB
2randomMasu305.txt 104 ms 23460 KB
2randomMasu306.txt 103 ms 23580 KB
2randomMasu307.txt 108 ms 23592 KB
2randomMasu308.txt 109 ms 23796 KB
2randomMasu309.txt 107 ms 23840 KB
2randomMasu500.txt 215 ms 48416 KB
2randomMasu501.txt 218 ms 48552 KB
2randomMasu502.txt 218 ms 48676 KB
2randomMasu503.txt 224 ms 48920 KB
2randomMasu504.txt 225 ms 49056 KB
2randomMasu505.txt 223 ms 49196 KB
2randomMasu506.txt 225 ms 49368 KB
2randomMasu507.txt 227 ms 49572 KB
2randomMasu508.txt 225 ms 49700 KB
2randomMasu509.txt 237 ms 49892 KB
2randomMasu740.txt 433 ms 96044 KB
2randomMasu741.txt 435 ms 96240 KB
2randomMasu742.txt 442 ms 96428 KB
2randomMasu743.txt 431 ms 96740 KB
2randomMasu744.txt 439 ms 96924 KB
2randomMasu745.txt 439 ms 97188 KB
2randomMasu746.txt 428 ms 97444 KB
2randomMasu747.txt 433 ms 97632 KB
2randomMasu748.txt 448 ms 97824 KB
2randomMasu749.txt 442 ms 98088 KB
2randomMasu750.txt 441 ms 98340 KB
2randomMasu750b.txt 363 ms 98332 KB
2sample3.txt 36 ms 8612 KB