# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
71645 | imsifile | Lokahian Rampart (FXCUP3_lokahia) | C++98 | 1256 ms | 178176 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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];
}
#include "dowoon.h"
static int N, M, ba[1010][1010], my, no, xx[4]={1,-1,0,0}, yy[4]={0,0,1,-1};
static void dfs(int x, int y, int hx, int hy){
if(x<=0 || y<=0 || x>N || y>M) return;
if(ba[x][y]) return;
if(Ask(x,y,hx,hy)) ba[x][y]=1, my++;
else{ ba[x][y]=-1; no++; return; }
for(int i=0; i<4; i++) dfs(x+xx[i], y+yy[i], hx, hy);
}
int Guess(int N_, int M_) {
N=N_, M=M_;
for(int j=1; j<M; j++){
for(int i=1; i<=N; i++){
if(2*no >= N*M) return 0;
if(ba[i][j] || ba[i][j+1]) continue;
int st=i, k, fl=0;
for(k=st; k<=N; k++){
if(ba[k][j] || ba[k][j+1]) break;
int a = Ask(k,j,k,j+1);
if(a){ fl=1; break; }
}
if(!fl){
i=k-1;
while(--k >= st) ba[k][j]=-1, no++;
continue;
}
ba[k][j]=ba[k][j+1]=1; my=2;
for(int k2=k-1; k2>=st; k2--){
int a = Ask(k2,j,k2+1,j);
if(a) ba[k2][j]=1, ba[k2][j+1]=-1, my++, no++;
else{
ba[k2][j]=-1, no++;
while(--k2 >= st) ba[k2][j]=-1, no++;
break;
}
}
dfs(k+1, j, k, j);
dfs(k+1, j+1, k, j);
dfs(k, j+2, k, j);
dfs(k-1, j+1, k, j);
if(my*2 > N*M) return 1;
no+=my, my=0;
i=k-1;
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |