oj.uz

Submission #71649

# Submission time Handle Problem Language Result Execution time Memory
71649 2018-08-25T09:46:36 Z imsifile Lokahian Rampart (FXCUP3_lokahia) C++
30 / 100
 1488 ms 210688 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 <memory.h>

static int N, M, xx[4]={1,-1,0,0}, yy[4]={0,0,1,-1};
int hist[1010][1010][2][2], ba[1010][1010], sz;

int myAsk(int r1, int c1, int r2, int c2){
	if(r2<=0 || c2<=0 || r2>N || c2>M) return 0;
	if(c2<c1) c1=c2, c2=c1+1;
	if(r2<r1) r1=r2, r2=r1+1;
	if(hist[r1][c1][r2-r1][c2-c1]>=0) return hist[r1][c1][r2-r1][c2-c1];
	return hist[r1][c1][r2-r1][c2-c1]=Ask(r1,c1,r2,c2);
}

void dfs(int x, int y){
	if(x<=0 || y<=0 || x>N || y>M) return;
	if(ba[x][y]) return;
	ba[x][y]=1, sz++;

	for(int i=0; i<4; i++){
		if(myAsk(x,y,x+xx[i],y+yy[i])) dfs(x+xx[i], y+yy[i]);
	}
}

int Guess(int N_, int M_) {
	N=N_, M=M_;
	memset(hist, -1, sizeof(hist));
	for(int i=1; i<=N; i++){
		for(int j=1; j<=M; j++){
			sz=0; dfs(i,j);
			if(sz*2 > N*M) return 1;
		}
	}
	return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16736 KB Correct
2 Correct 16 ms 32884 KB Correct
3 Correct 31 ms 33192 KB Correct
4 Correct 91 ms 39844 KB Correct
5 Correct 110 ms 46352 KB Correct
6 Correct 353 ms 86808 KB Correct
7 Correct 430 ms 128908 KB Correct
8 Correct 459 ms 169760 KB Correct
9 Correct 427 ms 208968 KB Correct

Subtask #2
17.0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16736 KB Correct
2 Correct 16 ms 32884 KB Correct
3 Correct 31 ms 33192 KB Correct
4 Correct 91 ms 39844 KB Correct
5 Correct 110 ms 46352 KB Correct
6 Correct 353 ms 86808 KB Correct
7 Correct 430 ms 128908 KB Correct
8 Correct 459 ms 169760 KB Correct
9 Correct 427 ms 208968 KB Correct
10 Partially correct 855 ms 208968 KB Partially correct : C/MN = 1.550
11 Partially correct 103 ms 208968 KB Partially correct : C/MN = 1.500
12 Correct 43 ms 208968 KB Correct
13 Partially correct 20 ms 208968 KB Partially correct : C/MN = 1.417
14 Partially correct 19 ms 208968 KB Partially correct : C/MN = 1.333
15 Partially correct 17 ms 208968 KB Partially correct : C/MN = 1.300
16 Partially correct 18 ms 208968 KB Partially correct : C/MN = 1.250
17 Partially correct 18 ms 208968 KB Partially correct : C/MN = 1.167
18 Correct 19 ms 208968 KB Correct
19 Partially correct 1488 ms 209828 KB Partially correct : C/MN = 1.400
20 Correct 18 ms 210688 KB Correct
21 Partially correct 20 ms 210688 KB Partially correct : C/MN = 1.280
22 Partially correct 19 ms 210688 KB Partially correct : C/MN = 1.250
23 Partially correct 21 ms 210688 KB Partially correct : C/MN = 1.496
24 Partially correct 35 ms 210688 KB Partially correct : C/MN = 1.663
25 Partially correct 26 ms 210688 KB Partially correct : C/MN = 1.980
26 Partially correct 41 ms 210688 KB Partially correct : C/MN = 1.674
27 Partially correct 63 ms 210688 KB Partially correct : C/MN = 1.291
28 Partially correct 64 ms 210688 KB Partially correct : C/MN = 1.831
29 Partially correct 103 ms 210688 KB Partially correct : C/MN = 1.841
30 Partially correct 134 ms 210688 KB Partially correct : C/MN = 1.709
31 Partially correct 442 ms 210688 KB Partially correct : C/MN = 1.649
32 Partially correct 368 ms 210688 KB Partially correct : C/MN = 1.278
33 Partially correct 431 ms 210688 KB Partially correct : C/MN = 1.998
34 Partially correct 390 ms 210688 KB Partially correct : C/MN = 1.263
35 Partially correct 462 ms 210688 KB Partially correct : C/MN = 1.998
36 Partially correct 531 ms 210688 KB Partially correct : C/MN = 1.998
37 Partially correct 351 ms 210688 KB Partially correct : C/MN = 1.800
38 Partially correct 398 ms 210688 KB Partially correct : C/MN = 1.798
39 Partially correct 243 ms 210688 KB Partially correct : C/MN = 1.651
40 Partially correct 248 ms 210688 KB Partially correct : C/MN = 1.472
41 Partially correct 439 ms 210688 KB Partially correct : C/MN = 1.540
42 Partially correct 357 ms 210688 KB Partially correct : C/MN = 1.998
43 Partially correct 513 ms 210688 KB Partially correct : C/MN = 1.752
44 Partially correct 187 ms 210688 KB Partially correct : C/MN = 1.600
45 Partially correct 176 ms 210688 KB Partially correct : C/MN = 1.600
46 Partially correct 413 ms 210688 KB Partially correct : C/MN = 1.499