#include "cave.h"
#include "bits/stdc++.h"
using namespace std;
const int nax = 5010;
int already[nax], query[nax], which[nax], is_already[nax];
void exploreCave(int N)
{
auto get_col = [&](int i) {
fill(query, query + N, 0);
for (int i = 0; i < N; i++)
if (is_already[i]) query[i] = already[i];
int ans = tryCombination(query);
return !(ans == -1 || ans > i);
};
function<void(int, int, int, int)> rek = [&](int where, int l, int r, int col) {
if (l == r) {
is_already[l] = 1;
already[l] = col;
which[l] = where;
return;
}
fill(query, query + N, 0);
int m = (l + r) / 2;
for (int i = 0; i < N; i++) {
if (l <= i && i <= m) query[i] = col;
else query[i] = col ^ 1;
}
for (int i = 0; i < N; i++)
if (is_already[i]) query[i] = already[i];
int ans = tryCombination(query);
if (ans == -1 || ans > where) rek(where, l, m, col);
else rek(where, m + 1, r, col);
};
for (int i = 0; i < N; i++) {
rek(i, 0, N - 1, get_col(i));
}
answer(already, which);
}
