#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 500;
const int M = 2 * maxN * maxN;
vector<int> g[maxN];
char vis[M];
int good[M];
int d[M];
int siz[M];
int pos[M];
//0 if it's officer's turn, 1 if robber's one
int enc(int officerPos, int robberPos, int whoseTurn) {
return whoseTurn * maxN * maxN + officerPos * maxN + robberPos;
}
inline void tryTo(int cur, int i) {
if (good[i] == -1) {
d[i]++;
pos[i] = cur;
}
}
inline void expand(int cur) {
if (d[cur] == siz[cur] || (cur / (maxN * maxN) == 0 && d[cur]))
good[cur] = pos[cur];
if (good[cur] != -1) {
int officerPos = cur % (maxN * maxN) / maxN;
int robberPos = cur % maxN;
if (cur / (maxN * maxN)) { //robber's turn
tryTo(cur, enc(officerPos, robberPos, 0));
if (good[enc(officerPos, robberPos, 0)] == -1)
expand(enc(officerPos, robberPos, 0));
for (int i : g[officerPos]) {
tryTo(cur, enc(i, robberPos, 0));
if (good[enc(i, robberPos, 0)] == -1)
expand(enc(i, robberPos, 0));
}
} else { //officer's turn
for (int i : g[robberPos]) {
tryTo(cur, enc(officerPos, i, 1));
if (good[enc(officerPos, i, 1)] == -1)
expand(enc(officerPos, i, 1));
}
}
}
}
int loc;
int start(int N, bool A[MAX_N][MAX_N]) {
memset(siz, 0, sizeof siz);
for (int i = 0; i < M; i++)
pos[i] = -2;
memset(good, -1, sizeof good);
memset(d, 0, sizeof d);
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (A[i][j])
g[i].push_back(j);
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (i != j) {
siz[enc(i, j, 0)]++;
siz[enc(i, j, 0)] += g[i].size();
siz[enc(i, j, 1)] += g[j].size();
}
for (int i = 0; i < N; i++) {
expand(enc(i, i, 0));
expand(enc(i, i, 1));
}
for (int i = 0; i < N; i++) {
bool no = 0;
for (int j = 0; j < N; j++)
no |= good[enc(i, j, 0)] == -1;
if (!no) {
loc = i;
return i;
}
}
return -1;
}
int nextMove(int R) {
//cout << loc << " " << R << endl;
loc = good[enc(loc, R, 0)] % (maxN * maxN) / maxN;
return loc;
}
