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