Submission #72556

#TimeUsernameProblemLanguageResultExecution timeMemory
72556imsifileLokahian Rampart (FXCUP3_lokahia)C++17
13 / 100
1483 ms178528 KiB
#include "sungjin.h" static int N, M, ba[1010][1010], chk[1010][1010], xx[4]={1,-1,0,0}, yy[4]={0,0,1,-1}; // DURL static void dfs1(int x, int y){ if(x<0 || y<0 || x>N+1 || y>M+1) return; if(chk[x][y]) return; chk[x][y]=-1; for(int i=0; i<4; i++){ if(ba[x][y]&(1<<i)) continue; dfs1(x+xx[i], y+yy[i]); } } static int col; static void dfs2(int x, int y){ if(x<=0 || y<=0 || x>N || y>M) return; if(chk[x][y]) return; chk[x][y]=col; for(int i=0; i<4; i++) dfs2(x+xx[i], y+yy[i]); } void Init(int N_, int M_, int W, int R[], int C[], int dir[]) { N=N_, M=M_; for(int i=W; i--;){ if(dir[i]==1) ba[R[i]][C[i]+1] |= 1<<3; if(dir[i]==2) ba[R[i]][C[i]-1] |= 1<<2; if(dir[i]==3) ba[R[i]+1][C[i]] |= 1<<1; if(dir[i]==4) ba[R[i]-1][C[i]] |= 1<<0; } dfs1(0,0); for(int i=1; i<=N; i++){ for(int j=1; j<=M; j++){ if(chk[i][j]) continue; ++col; dfs2(i,j); } } } int WereSameTerritory(int R1, int C1, int R2, int C2) { if(chk[R1][C1]<0 || chk[R2][C2]<0) return 0; return chk[R1][C1] == chk[R2][C2]; }
// ainta & cki86201's code (https://oj.uz/submission/72484) #include "dowoon.h" int w[1010][1010], c1, c2; void Put(int x, int y, int c) { if (w[x][y])return; w[x][y] = c; if (c == 1)c1++; else c2++; } int Guess(int N, int M) { int i, j; for (i = 1; i <= N; i++) { for (j = 1; j <= M; j++) { if (c1 * 2 > N*M)return 1; if (c2 * 2 >= N*M)return 0; if (w[i][j]) { if (w[i][j] == 2) continue; if (j + 1 <= M && !w[i][j + 1]) { if (Ask(i, j, i, j + 1))Put(i,j+1,1); else Put(i,j+1,2); } if (i + 1 <= N && !w[i + 1][j]) { if (Ask(i, j, i + 1, j))Put(i+1,j,1); else Put(i+1,j,2); } continue; } if (i == N && j == M) { w[i][j] = 2; continue; } if (i == N) { if (Ask(i, j, i, j + 1)) { Put(i, j, 1); Put(i, j + 1, 1); } else Put(i, j, 2); continue; } if (j == M) { if (Ask(i, j, i + 1, j)) { Put(i, j, 1); Put(i + 1, j, 1); } else Put(i, j, 2); continue; } int t1 = Ask(i, j, i + 1, j); int t2 = Ask(i, j, i, j + 1); if (t1 || t2) { Put(i, j, 1); if (t1)Put(i + 1, j, 1); else Put(i + 1, j, 2); if (t2)Put(i, j + 1, 1); else Put(i, j + 1, 2); } else { Put(i, j, 2); } } } if (c1 * 2 > N*M)return 1; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...