#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
void exploreCave(int N) {
int b[N];
bool locked[N];
int s[N],d[N];
vector<int>unlocked;
memset(locked,0,sizeof(locked));
for(int i=0;i<N;i++)
{
unlocked.clear();
for(int j=0;j<N;j++)
{
if(!locked[j])
{
b[j]=0;
unlocked.push_back(j);
}
}
int xd=tryCombination(b);
if(xd==i)
{
int low=0,high=unlocked.size()-1,mid,ans=0;
while(low<=high)
{
mid=(low+high)/2;
for(int j=0;j<(int)unlocked.size();j++)
{
if(j<=mid)b[unlocked[j]]=0;
else b[unlocked[j]]=1;
}
int r=tryCombination(b);
if(r==i)
{
ans=mid;
high=mid-1;
}
else low=mid+1;
}
b[unlocked[ans]]=1;
locked[unlocked[ans]]=1;
s[unlocked[ans]]=1;
d[unlocked[ans]]=i;
}
else
{
int low=0,high=unlocked.size()-1,mid,ans=0;
while(low<=high)
{
mid=(low+high)/2;
for(int j=0;j<(int)unlocked.size();j++)
{
if(j<=mid)b[unlocked[j]]=1;
else b[unlocked[j]]=0;
}
int r=tryCombination(b);
if(r==i)
{
ans=mid;
high=mid-1;
}
else low=mid+1;
}
b[unlocked[ans]]=0;
locked[unlocked[ans]]=1;
s[unlocked[ans]]=0;
d[unlocked[ans]]=i;
}
}
answer(s,d);
}
