oj.uz

Submission #71651

# Submission time Handle Problem Language Result Execution time Memory
71651 2018-08-25T09:47:44 Z imsifile Lokahian Rampart (FXCUP3_lokahia) C++
13 / 100
 657 ms 176216 KB 
#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"
    #include <stdlib.h>
     
    static int N, M, ba[1010][1010], my, no, xx[4]={1,-1,0,0}, yy[4]={0,0,1,-1};
     
    int myAsk(int r1, int c1, int r2, int c2){
    	if(ba[r1][c1]<0 || ba[r2][c2]<0) return 0;
    	if(!ba[r1][c1] && !ba[r2][c2]) return ba[r1][c1]==ba[r2][c2];
    	return Ask(r1,c1,r2,c2);
    }
     
    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(myAsk(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 i=N*M; i--;){
    		if(2*no >= N*M) return 0;
    		int r=rand()%N+1, c=rand()%(M-1)+1;
    		if(myAsk(r,c,r,c+1)){
    			ba[r][c]=1, my++;
    			ba[r][c+1]=1, my++;
    			dfs(r,c-1,r,c);
    			dfs(r,c+2,r,c);
    			dfs(r-1,c,r,c);
    			dfs(r-1,c+1,r,c);
    			dfs(r+1,c,r,c);
    			dfs(r+1,c+1,r,c);
    		}
    		if(my*2 > N*M) return 1;
    		no += my;
    	}
    	return 0;
    }

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 776 KB Correct
2 Correct 5 ms 1256 KB Correct
3 Correct 19 ms 1652 KB Correct
4 Correct 84 ms 16576 KB Correct
5 Correct 89 ms 16576 KB Correct
6 Correct 309 ms 67528 KB Correct
7 Correct 289 ms 95276 KB Correct
8 Correct 284 ms 141692 KB Correct
9 Correct 285 ms 176216 KB Correct

Subtask #2
0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 776 KB Correct
2 Correct 5 ms 1256 KB Correct
3 Correct 19 ms 1652 KB Correct
4 Correct 84 ms 16576 KB Correct
5 Correct 89 ms 16576 KB Correct
6 Correct 309 ms 67528 KB Correct
7 Correct 289 ms 95276 KB Correct
8 Correct 284 ms 141692 KB Correct
9 Correct 285 ms 176216 KB Correct
10 Runtime error 657 ms 176216 KB Execution failed because the return code was nonzero
11 Halted 0 ms 0 KB -