#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int n, correct[5010], d[5010], done, leftmost, s[5010];
bool mk[5010];
int process(int lo, int hi)
{
int m = (lo + hi) / 2;
for(int i = 0; i < n; i++)
if(!mk[i])
s[i] = 0;
for(int i = lo; i <= m; i++)
if(!mk[i])
s[i] = 1;
return tryCombination(s);
}
pair<int,int> search(int lo, int hi, int flag)
{
int m = (lo + hi) / 2;
if(lo == hi)
{
mk[leftmost] = true;
correct[lo] = flag;
d[lo] = leftmost;
return make_pair(lo,leftmost);
}
int pos = process(lo,hi);
if(pos > leftmost)
return search(lo,m,1);
else if(pos == leftmost)
return search(m+1,hi,1);
else
{
leftmost = pos;
return search(lo,m,0);
}
}
void exploreCave(int N) {
n = N;
for(int i = 0; i < n; i++)
{
pair<int,int> pr = search(0,n-1,0);
s[pr.first] = pr.second;
}
answer(s,d);
}
