#include <set>
#include "cave.h"
#include <iostream>
#include <vector>
using namespace std;
int nn;
vector<int>ind;
int check(int l,int r,int S[],bool val)
{
for (int i=l;i<=r;i++)
{
S[ind[i]]=val;
}
return tryCombination(S);
}
void unfill(int l,int r,int S[],bool val)
{
for (int i=l;i<=r;i++)
S[ind[i]]=val;
}
void ans(int d[],int S[])
{
for (int i=0;i<nn;i++)
{
S[i]^=1;
int z=tryCombination(S);
d[i]=z;
S[i]^=1;
}
answer(S,d);
exit(0);
}
void exploreCave(int n)
{
nn=n;
int d[n]={},S[n]={};
int x=-2;
for (int i=0;i<n;i++)
ind.push_back(i);
for (int i=0;i<n;i++)
{
if (x==-2)
x=tryCombination(S);
if (x==-1)
ans(d,S);
bool z=(x==i);
int st=0,en=ind.size()-1;
while (st!=en)
{
int mid=(st+en)/2;
x=check(st,mid,S,1);
if (x==-1)
ans(d,S);
unfill(st,mid,S,0);
if (z==0)
{
if (x==i)
en=mid;
else
st=mid+1;
}
else
{
if (x>i)
en=mid;
else
st=mid+1;
}
}
d[ind[st]]=i;
S[ind[st]]=z;
ind.erase(begin(ind)+st);
}
ans(d,S);
}
