oj.uz

Submission #72882

# Submission time Handle Problem Language Result Execution time Memory
72882 2018-08-27T07:13:06 Z ainta Lokahian Rampart (FXCUP3_lokahia) C++17
65 / 100
 1278 ms 185248 KB 
#include "sungjin.h"

static int X[1010][1010], Y[1010][1010], n, m, vis[1010][1010], U[1010][1010];

static int w[1010][1010][4], dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };

static int Rev[4] = { 1,0,3,2 };

void DFS(int x, int y) {
	if (x<0 || y<0 || x>n + 1 || y>m + 1 || vis[x][y])return;
	vis[x][y] = 1;
	for (int i = 0; i < 4; i++) {
		if(!w[x][y][i])DFS(x + dx[i], y + dy[i]);
	}
}


void Go(int x, int y, int col) {
	vis[x][y] = col;
	for (int i = 0; i < 4; i++) {
		int tx = x + dx[i], ty = y + dy[i];
		if(!vis[tx][ty])Go(x + dx[i], y + dy[i], col);
	}
}

void Init(int N, int M, int W, int R[], int C[], int dir[]) {
	int i, j, res = 0;
	n = N, m = M;
	for (i = 0; i < W; i++) {
		dir[i]--;
		w[R[i]+dx[dir[i]]][C[i]+dy[dir[i]]][Rev[dir[i]]] = 1;
	}
	DFS(0, 0);
	int cnt = 1;
	for (i = 1; i <= N; i++) {
		for (j = 1; j <= M; j++) {
			if (!vis[i][j]) {
				cnt++;
				Go(i, j, cnt);
			}
		}
	}
}

int WereSameTerritory(int R1, int C1, int R2, int C2) {
	if (vis[R1][C1] == vis[R2][C2] && vis[R1][C1] != 1)return 1;
	return 0;
}

#include "dowoon.h"


int UF[1010000], C[1010000], w[1010][1010], cc;

int nn, mm;

int Num(int x, int y) {
	return (x - 1)*mm + y;
}
int Find(int a) {
	if (a == UF[a])return a;
	return UF[a] = Find(UF[a]);
}
void Merge(int a, int b, int c, int d) {
	w[a][b] = w[c][d] = 1;
	int x = Num(a, b), y = Num(c, d);
	x = Find(x), y = Find(y);
	if(x!=y)UF[x] = y;
}

void Put(int a, int b, int c) {
	if (!w[a][b] && c == 2)cc++;
	w[a][b] = c;
}

int Guess(int N, int M) {
	int i, j;
	nn = N, mm = M;
	for (i = 1; i <= N*M; i++)UF[i] = i; 
	for (i = 1; i <= N; i++) {
		for (j = 1; j <= M; j++) {
			if (cc * 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);
			}
		}
	}
	for (i = 1; i <= N; i++)for (j = 1; j <= M; j++) {
		if (i + 1 <= N&&w[i][j] == 1 && w[i + 1][j] == 1)Merge(i, j, i + 1, j);
		if (j + 1 <= M&&w[i][j] == 1 && w[i][j + 1] == 1)Merge(i, j, i, j + 1);
	}
	for (i = 1; i <= N*M; i++)C[Find(i)]++;
	for (i = 1; i <= N*M; i++)if (C[i] * 2 > N*M)return 1;
	return 0;
}

Compilation message

sungjin.cpp: In function 'void Init(int, int, int, int*, int*, int*)':
sungjin.cpp:27:12: warning: unused variable 'res' [-Wunused-variable]
  int i, j, res = 0;
            ^~~
sungjin.cpp: At global scope:
sungjin.cpp:3:65: warning: 'U' defined but not used [-Wunused-variable]
 static int X[1010][1010], Y[1010][1010], n, m, vis[1010][1010], U[1010][1010];
                                                                 ^
sungjin.cpp:3:27: warning: 'Y' defined but not used [-Wunused-variable]
 static int X[1010][1010], Y[1010][1010], n, m, vis[1010][1010], U[1010][1010];
                           ^
sungjin.cpp:3:12: warning: 'X' defined but not used [-Wunused-variable]
 static int X[1010][1010], Y[1010][1010], n, m, vis[1010][1010], U[1010][1010];
            ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 916 KB Correct
2 Correct 4 ms 1108 KB Correct
3 Correct 19 ms 1604 KB Correct
4 Correct 75 ms 17728 KB Correct
5 Correct 86 ms 17728 KB Correct
6 Correct 324 ms 91168 KB Correct
7 Correct 284 ms 110568 KB Correct
8 Correct 317 ms 145796 KB Correct
9 Correct 267 ms 181024 KB Correct

Subtask #2
52.0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 916 KB Correct
2 Correct 4 ms 1108 KB Correct
3 Correct 19 ms 1604 KB Correct
4 Correct 75 ms 17728 KB Correct
5 Correct 86 ms 17728 KB Correct
6 Correct 324 ms 91168 KB Correct
7 Correct 284 ms 110568 KB Correct
8 Correct 317 ms 145796 KB Correct
9 Correct 267 ms 181024 KB Correct
10 Correct 713 ms 181024 KB Correct
11 Partially correct 49 ms 181024 KB Partially correct : C/MN = 1.250
12 Correct 24 ms 181024 KB Correct
13 Correct 6 ms 181024 KB Correct
14 Partially correct 4 ms 181024 KB Partially correct : C/MN = 1.222
15 Partially correct 4 ms 181024 KB Partially correct : C/MN = 1.100
16 Correct 4 ms 181024 KB Correct
17 Correct 4 ms 181024 KB Correct
18 Correct 4 ms 181024 KB Correct
19 Partially correct 1278 ms 181024 KB Partially correct : C/MN = 1.120
20 Correct 6 ms 181024 KB Correct
21 Partially correct 4 ms 181024 KB Partially correct : C/MN = 1.160
22 Partially correct 4 ms 181024 KB Partially correct : C/MN = 1.060
23 Correct 5 ms 181024 KB Correct
24 Partially correct 22 ms 181024 KB Partially correct : C/MN = 1.002
25 Partially correct 12 ms 181024 KB Partially correct : C/MN = 1.244
26 Partially correct 26 ms 181024 KB Partially correct : C/MN = 1.089
27 Partially correct 52 ms 181024 KB Partially correct : C/MN = 1.169
28 Partially correct 52 ms 181024 KB Partially correct : C/MN = 1.014
29 Partially correct 67 ms 181024 KB Partially correct : C/MN = 1.024
30 Partially correct 96 ms 181024 KB Partially correct : C/MN = 1.077
31 Partially correct 362 ms 181024 KB Partially correct : C/MN = 1.077
32 Partially correct 348 ms 181024 KB Partially correct : C/MN = 1.141
33 Partially correct 324 ms 181024 KB Partially correct : C/MN = 1.199
34 Partially correct 353 ms 181024 KB Partially correct : C/MN = 1.149
35 Correct 389 ms 181024 KB Correct
36 Correct 365 ms 183136 KB Correct
37 Correct 361 ms 185248 KB Correct
38 Correct 341 ms 185248 KB Correct
39 Partially correct 223 ms 185248 KB Partially correct : C/MN = 1.104
40 Partially correct 227 ms 185248 KB Partially correct : C/MN = 1.132
41 Partially correct 335 ms 185248 KB Partially correct : C/MN = 1.102
42 Partially correct 297 ms 185248 KB Partially correct : C/MN = 1.000
43 Partially correct 381 ms 185248 KB Partially correct : C/MN = 1.000
44 Partially correct 132 ms 185248 KB Partially correct : C/MN = 1.080
45 Partially correct 129 ms 185248 KB Partially correct : C/MN = 1.040
46 Partially correct 341 ms 185248 KB Partially correct : C/MN = 1.499