#include <bits/stdc++.h>
#include "cave.h"
const int MAXN = 5050;
int s[MAXN], d[MAXN], aux[MAXN];
void exploreCave(int n)
{
memset(s, -1, sizeof s);
for(int i = 1; i <= n; ++i)
{
int beg = 1, end = n, mid, x, y;
while(beg < end)
{
mid = (beg + end) >> 1;
for(int j = 1; j <= n; ++j)
aux[j] = s[j];
for(int j = 1; j <= mid; ++j)
if(aux[j] == -1)
aux[j] = 0;
x = tryCombination(aux);
for(int j = 1; j <= n; ++j)
aux[j] = s[j];
for(int j = 1; j <= mid; ++j)
if(aux[j] == -1)
aux[j] = 1;
y = tryCombination(aux);
if(x > i && y > i)
beg = mid + 1;
else
end = mid;
}
d[i] = beg;
for(int j = 1; j <= n; ++j)
aux[j] = s[j];
aux[d[i]] = 0;
x = tryCombination(aux);
if(x >= i)
s[d[i]] = 0;
else
s[d[i]] = 1;
}
answer(s, d);
}
