#include "cave.h"
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define mp make_pair
const int MAX=1e5;
void exploreCave(int N)
{
/* ... */
vector<int> vec;
int cur,lol,shi[MAX],pos[MAX];
for(int A=0;A<N;A++)
{
shi[A]=0;
pos[A]=0;
vec.pb(A);
}
for(int A=0;A<N;A++)
{
cur=tryCombination(shi);
if(cur==-1)
{
for(auto B:vec)
{
shi[B]=1;
pos[B]=tryCombination(shi);
shi[B]=0;
}
answer(shi,pos);
return ;
}
/*for(auto B:vec)
{
shi[B]=1;
lol=tryCombination(shi);
if(lol>cur or lol==-1)
{
shi[B]=1;
pos[B]=cur;
vec.erase(lower_bound(vec.begin(),vec.end(),B));
break;
}
else if(lol<cur)
{
shi[B]=0;
pos[B]=lol;
vec.erase(lower_bound(vec.begin(),vec.end(),B));
break;
}
shi[B]=0;
}*/
int low=0,high=vec.size()-1,mid,res=0;
while(low<=high)
{
mid=(low+high)/2;
for(auto B:vec)
{
if(B<=vec[mid])
shi[B]=1;
else
shi[B]=0;
}
lol=tryCombination(shi);
if(lol!=cur)
{
res=mid;
high=mid-1;
}
else
low=mid+1;
for(auto B:vec)
shi[B]=0;
}
int B=vec[res];
shi[B]=1;
lol=tryCombination(shi);
if(lol>cur or lol==-1)
{
shi[B]=1;
pos[B]=cur;
vec.erase(lower_bound(vec.begin(),vec.end(),B));
}
else if(lol<cur)
{
shi[B]=0;
pos[B]=lol;
vec.erase(lower_bound(vec.begin(),vec.end(),B));
}
}
answer(shi,pos);
return ;
}
