oj.uz

Submission #72915

# Submission time Handle Problem Language Result Execution time Memory
72915 2018-08-27T08:27:16 Z ainta Lokahian Rampart (FXCUP3_lokahia) C++17
88 / 100
 1271 ms 217384 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"
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

static int UF[1010000], C[1010000], w[1010][1010], sum, vis[1010][1010];

static int n, m, cnt, dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };

int Num(int x, int y) {
	return (x - 1)*m + y;
}
int Ask2(int a, int b, int c, int d) {
	if (sum * 2 >= n*m || cnt * 2 > n*m)return 0;
	return Ask(a, b, c, d);
}
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;
}

static struct point {
	int x, y;
}P[1010][1010];

void Put(int a, int b, int c) {
	if (sum * 2 >= n*m || cnt * 2 > n*m)return;
	if (w[a][b])return;
	w[a][b] = c;
	point tp = P[a][b];
	if (tp.x && c == 1) {
		Put(tp.x, tp.y, 2);
	}
	if (c == 2) {
		if (!tp.x || w[tp.x][tp.y] == 2) sum++;
	}
}

void DDFS(int x, int y) {
	int i;
	vis[x][y] = 1;
	cnt++;
	for (i = 0; i < 4; i++) {
		int tx = x + dx[i], ty = y + dy[i];
		if (1 > tx || tx > n || 1 > ty || ty > m ||vis[tx][ty]||w[tx][ty]==2)continue;
		if (!w[tx][ty]) {
			if (Ask2(x, y, tx, ty)) Put(tx, ty, 1);
			else Put(tx, ty, 2);
		}
		if (w[tx][ty] == 1 && !vis[tx][ty])DDFS(tx, ty);
	}
}


void Go(int x, int y) {
	cnt = 0;
	if (vis[x][y])return;
	if (n % 2 == 1 && m % 2 == 1 && x==n && y==m) {
		if (Ask2(x - 1, y, x, y)) {
			Put(x - 1, y, 1);
			Put(x, y, 1);
		}
		else{
			if (Ask2(x, y, x, y - 1)) {
				Put(x, y, 1);
				Put(x, y - 1, 1);
				Put(x - 1, y, 2);
			}
			else return;
		}
	}
	DDFS(x, y);
}

int Guess(int N, int M) {
	int i, j;
	n = N, m = M;
	vector<point>V;
	for (i = 1; i <= N*M; i++)UF[i] = i; 

	for (i = 1; i <= N; i++){
		for (j = 1; j < M; j += 2) {
			if (Ask2(i, j, i, j + 1)) {
				Put(i, j, 1);
				Put(i, j + 1, 1);
				V.push_back({ i, j });
			}
			else sum++;
			P[i][j] = { i,j + 1 };
			P[i][j + 1] = { i,j };
		}
	}
	if (M % 2 == 1) {
		for (i = 1; i < N; i+=2) {
			if (Ask2(i, M, i + 1, M)) {
				Put(i, M, 1);
				Put(i + 1, M, 1);
				V.push_back({ i, M });
			}
			else sum++;
			P[i][M] = { i + 1,M };
			P[i + 1][M] = { i,M };
		}
		if (N % 2 == 1) {
			V.push_back({ n,m });
		}
	}
	for (auto &t : V) {
		Go(t.x, t.y);
		if (cnt * 2 > n*m)return 1;
		sum += cnt;
		if (sum * 2 >= n*m)return 0;
	}
	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];
            ^

dowoon.cpp:7:25: warning: 'C' defined but not used [-Wunused-variable]
 static int UF[1010000], C[1010000], w[1010][1010], sum, vis[1010][1010];
                         ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 864 KB Correct
2 Correct 6 ms 1272 KB Correct
3 Correct 26 ms 1904 KB Correct
4 Correct 85 ms 21164 KB Correct
5 Correct 98 ms 24432 KB Correct
6 Correct 305 ms 99244 KB Correct
7 Correct 353 ms 129640 KB Correct
8 Correct 318 ms 162680 KB Correct
9 Correct 279 ms 192776 KB Correct

Subtask #2
75.0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 864 KB Correct
2 Correct 6 ms 1272 KB Correct
3 Correct 26 ms 1904 KB Correct
4 Correct 85 ms 21164 KB Correct
5 Correct 98 ms 24432 KB Correct
6 Correct 305 ms 99244 KB Correct
7 Correct 353 ms 129640 KB Correct
8 Correct 318 ms 162680 KB Correct
9 Correct 279 ms 192776 KB Correct
10 Correct 661 ms 192776 KB Correct
11 Partially correct 60 ms 192776 KB Partially correct : C/MN = 1.062
12 Correct 30 ms 192776 KB Correct
13 Correct 8 ms 192776 KB Correct
14 Correct 6 ms 192776 KB Correct
15 Partially correct 6 ms 192776 KB Partially correct : C/MN = 1.100
16 Correct 4 ms 192776 KB Correct
17 Partially correct 4 ms 192776 KB Partially correct : C/MN = 1.167
18 Correct 4 ms 192776 KB Correct
19 Correct 1271 ms 192776 KB Correct
20 Correct 6 ms 192776 KB Correct
21 Correct 4 ms 192776 KB Correct
22 Correct 6 ms 192776 KB Correct
23 Correct 8 ms 192776 KB Correct
24 Correct 34 ms 192776 KB Correct
25 Correct 16 ms 192776 KB Correct
26 Correct 31 ms 192776 KB Correct
27 Correct 94 ms 192776 KB Correct
28 Correct 70 ms 192776 KB Correct
29 Correct 89 ms 192776 KB Correct
30 Correct 104 ms 192776 KB Correct
31 Correct 409 ms 192776 KB Correct
32 Correct 438 ms 192776 KB Correct
33 Correct 314 ms 192776 KB Correct
34 Correct 404 ms 192776 KB Correct
35 Correct 383 ms 192776 KB Correct
36 Correct 388 ms 205080 KB Correct
37 Correct 375 ms 217384 KB Correct
38 Correct 373 ms 217384 KB Correct
39 Correct 234 ms 217384 KB Correct
40 Correct 235 ms 217384 KB Correct
41 Correct 349 ms 217384 KB Correct
42 Partially correct 371 ms 217384 KB Partially correct : C/MN = 1.000
43 Correct 427 ms 217384 KB Correct
44 Correct 141 ms 217384 KB Correct
45 Partially correct 144 ms 217384 KB Partially correct : C/MN = 1.040
46 Correct 356 ms 217384 KB Correct