#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 = 0; i < n; ++i)
{
int beg = 0, end = n - 1, mid, x, y;
for(int j = 0; j < n; ++j)
aux[j] = s[j];
for(int j = 0; j < n; ++j)
if(aux[j] == -1)
aux[j] = 0;
x = tryCombination(aux);
if(x == -1)
x = n;
while(beg < end)
{
mid = (beg + end) >> 1;
for(int j = 0; j < n; ++j)
aux[j] = s[j];
for(int j = beg; j <= mid; ++j)
if(aux[j] == -1)
aux[j] = 1;
for(int j = 0; j < n; ++j)
if(aux[j] == -1)
aux[j] = 0;
y = tryCombination(aux);
if(y == -1)
y = n;
if((x > i && y > i) || (x == i && y == i))
beg = mid + 1;
else
end = mid;
}
d[beg] = i;
if(x == -1)
x = n;
if(x > i)
s[beg] = 0;
else
s[beg] = 1;
}
answer(s, d);
}
