#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int n){
int ans[n+5], pos[n+5], type[n+5];
vector<int> vect(n);
for (int i=0; i<n; ++i)ans[i]=pos[i]=-1, vect[i]=i;
for (int p=0, c; p<n; ++p){
bool t=0;
for (int i=0; i<n; ++i)type[i]=(pos[i]==-1?0:pos[i]);
c=tryCombination(type);
if (c==p){
for (int i=0; i<n; ++i)type[i]=(pos[i]==-1?1:pos[i]);
c=tryCombination(type);
t=1;
}
int low=-1, high=vect.size();
while (low+1<high){
int mid=(low+high)/2;
for (int i=0; i<vect[mid]; ++i)type[i]=(pos[i]==-1?!t:pos[i]);
for (int i=vect[mid]; i<n; ++i)type[i]=(pos[i]==-1?t:pos[i]);
c=tryCombination(type);
if (c==-1||c>p)low=mid;
else high=mid;
}
pos[vect[low]]=t;
ans[vect[low]]=p;
vect.erase(next(vect.begin(), low));
}
answer(pos, ans);
}
