#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 ddx[4] = { 1,1,-1,-1 }, ddy[4] = { 1,-1,1,-1 };
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);
}
for (int i = 0; i < 4; i++) {
int tx = x + ddx[i], ty = y + ddy[i];
if (!vis[tx][ty])Go(x + ddx[i], y + ddy[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]][C[i]][dir[i]] = 1;
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];
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) {
int x = Num(a, b), y = Num(c, d);
x = Find(x), y = Find(y);
if(x!=y)UF[x] = y;
}
/*void Put(int x, int y, int c) {
if (w[x][y])return;
tot++;
w[x][y] = c;
C[c]++;
}*/
int Guess(int N, int M) {
int i, j;
nn = N, mm = M;
/* n = N, m = M;
for (i = 1; i <= N; i++) {
for (j = 1; j <= M; j++) {
if (w[i][j]) {
if (w[i][j] == 1) continue;
if (j + 1 <= M && !w[i][j + 1]) {
if (Ask(i, j, i, j + 1))Put(i,j+1,w[i][j]);
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);
}
}
}
if (c1 * 2 > N*M)return 1;
return 0;*/
for(i=1;i<=N*M;i++)UF[i]=i;
for (i = 1; i <= N; i++) {
for (j = 1; j <= M; j++) {
if (i + 1 <= N && Ask(i, j, i + 1, j))Merge(i, j, i + 1, j);
if (j + 1 <= M && Ask(i, j, i , j + 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:32: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];
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
864 KB |
Correct |
| 2 |
Correct |
6 ms |
1224 KB |
Correct |
| 3 |
Correct |
19 ms |
1656 KB |
Correct |
| 4 |
Correct |
87 ms |
18088 KB |
Correct |
| 5 |
Correct |
96 ms |
18088 KB |
Correct |
| 6 |
Correct |
399 ms |
87336 KB |
Correct |
| 7 |
Correct |
345 ms |
104452 KB |
Correct |
| 8 |
Correct |
376 ms |
145924 KB |
Correct |
| 9 |
Correct |
341 ms |
184632 KB |
Correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
864 KB |
Correct |
| 2 |
Correct |
6 ms |
1224 KB |
Correct |
| 3 |
Correct |
19 ms |
1656 KB |
Correct |
| 4 |
Correct |
87 ms |
18088 KB |
Correct |
| 5 |
Correct |
96 ms |
18088 KB |
Correct |
| 6 |
Correct |
399 ms |
87336 KB |
Correct |
| 7 |
Correct |
345 ms |
104452 KB |
Correct |
| 8 |
Correct |
376 ms |
145924 KB |
Correct |
| 9 |
Correct |
341 ms |
184632 KB |
Correct |
| 10 |
Partially correct |
1029 ms |
184632 KB |
Partially correct : C/MN = 1.550 |
| 11 |
Partially correct |
59 ms |
184632 KB |
Partially correct : C/MN = 1.500 |
| 12 |
Partially correct |
41 ms |
184632 KB |
Partially correct : C/MN = 1.467 |
| 13 |
Partially correct |
8 ms |
184632 KB |
Partially correct : C/MN = 1.417 |
| 14 |
Partially correct |
4 ms |
184632 KB |
Partially correct : C/MN = 1.333 |
| 15 |
Partially correct |
7 ms |
184632 KB |
Partially correct : C/MN = 1.300 |
| 16 |
Partially correct |
5 ms |
184632 KB |
Partially correct : C/MN = 1.250 |
| 17 |
Partially correct |
4 ms |
184632 KB |
Partially correct : C/MN = 1.167 |
| 18 |
Correct |
4 ms |
184632 KB |
Correct |
| 19 |
Partially correct |
1480 ms |
184632 KB |
Partially correct : C/MN = 1.600 |
| 20 |
Correct |
6 ms |
184632 KB |
Correct |
| 21 |
Runtime error |
2 ms |
92316 KB |
Execution failed because the return code was nonzero |
| 22 |
Halted |
0 ms |
0 KB |
- |
