#include<iostream>
#include<vector>
#include"cave.h"
using namespace std;
int S[5001], D[5001];
int curS[5001];
bool prc[5001];
void exploreCave(int N)
{
fill(S, S+5000, 0);
fill(D, D+5000, 0);
fill(curS, curS+5000, 0);
fill(prc, prc+5000, false);
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
if(prc[j]) curS[j] = S[j];
else curS[j] = 0;
}
int open;
int cur = tryCombination(curS);
if(cur > i || cur == -1) open = 0;
else open = 1;
int l = 0, r = N-1;
while(l < r)
{
int m = (l+r)/2;
for(int i = 0; i < N; i++)
{
if(prc[i]) curS[i] = S[i];
else
{
if(i <= m) curS[i] = open;
else curS[i] = abs(open-1);
}
}
int ans = tryCombination(curS);
if(ans > i || ans == -1) r = m;
else l = m+1;
}
prc[l] = true;
S[i] = open;
D[i] = l;
}
answer(S, D);
}
