oj.uz

Submission #71645

# Submission time Handle Problem Language Result Execution time Memory
71645 2018-08-25T09:42:35 Z imsifile Lokahian Rampart (FXCUP3_lokahia) C++
100 / 100
 1256 ms 178176 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"

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;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 752 KB Correct
2 Correct 4 ms 952 KB Correct
3 Correct 18 ms 1516 KB Correct
4 Correct 77 ms 16696 KB Correct
5 Correct 71 ms 16696 KB Correct
6 Correct 288 ms 68380 KB Correct
7 Correct 304 ms 96692 KB Correct
8 Correct 327 ms 141948 KB Correct
9 Correct 252 ms 176880 KB Correct

Subtask #2
87.0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 752 KB Correct
2 Correct 4 ms 952 KB Correct
3 Correct 18 ms 1516 KB Correct
4 Correct 77 ms 16696 KB Correct
5 Correct 71 ms 16696 KB Correct
6 Correct 288 ms 68380 KB Correct
7 Correct 304 ms 96692 KB Correct
8 Correct 327 ms 141948 KB Correct
9 Correct 252 ms 176880 KB Correct
10 Correct 684 ms 176880 KB Correct
11 Correct 56 ms 176880 KB Correct
12 Correct 24 ms 176880 KB Correct
13 Correct 6 ms 176880 KB Correct
14 Correct 4 ms 176880 KB Correct
15 Correct 5 ms 176880 KB Correct
16 Correct 5 ms 176880 KB Correct
17 Correct 4 ms 176880 KB Correct
18 Correct 4 ms 176880 KB Correct
19 Correct 1256 ms 177528 KB Correct
20 Correct 6 ms 178176 KB Correct
21 Correct 4 ms 178176 KB Correct
22 Correct 4 ms 178176 KB Correct
23 Correct 7 ms 178176 KB Correct
24 Correct 33 ms 178176 KB Correct
25 Correct 12 ms 178176 KB Correct
26 Correct 32 ms 178176 KB Correct
27 Correct 81 ms 178176 KB Correct
28 Correct 90 ms 178176 KB Correct
29 Correct 92 ms 178176 KB Correct
30 Correct 120 ms 178176 KB Correct
31 Correct 435 ms 178176 KB Correct
32 Correct 371 ms 178176 KB Correct
33 Correct 311 ms 178176 KB Correct
34 Correct 349 ms 178176 KB Correct
35 Correct 364 ms 178176 KB Correct
36 Correct 454 ms 178176 KB Correct
37 Correct 388 ms 178176 KB Correct
38 Correct 349 ms 178176 KB Correct
39 Correct 234 ms 178176 KB Correct
40 Correct 247 ms 178176 KB Correct
41 Correct 316 ms 178176 KB Correct
42 Correct 292 ms 178176 KB Correct
43 Correct 450 ms 178176 KB Correct
44 Correct 179 ms 178176 KB Correct
45 Correct 165 ms 178176 KB Correct
46 Correct 432 ms 178176 KB Correct