#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int N) {
int S[5000] = {}, f[5000], s[5000];
memset(f, -1, sizeof f);
memset(s, -1, sizeof s);
function<void(int, int, int, int)> dac = [&](int l, int r, int i, int t)
{
if (l == r)
{
f[l] = !t;
s[l] = i;
return;
}
int mid = (l + r) >> 1;
for (int i = 0; i < N; i++)
{
if (f[i] != -1) S[i] = f[i];
else
{
if (i >= l && i <= mid) S[i] = t;
else S[i] = !t;
}
}
int k = tryCombination(S);
if (k == -1 || k > i) dac(mid + 1, r, i, t);
else dac(l, mid, i, t);
};
int mid = (N - 1) / 2;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (f[j] == -1) S[j] = 0;
else S[j] = f[j];
}
int k = tryCombination(S);
if (k == -1 || k > i)
{
dac(0, N - 1, i, 1);
}
else
{
dac(0, N - 1, i, 0);
}
}
answer(f, s);
}
