#include <set>
#include "cave.h"
#include <iostream>
using namespace std;
int const MAXN=5e3+10;
bool vis[MAXN]={};
int nn;
int check(int l,int r,int S[],bool val)
{
for (int i=l;i<=r;i++)
{
if (vis[i])
continue;
S[i]=val;
}
return tryCombination(S);
}
void unfill(int l,int r,int S[],bool val)
{
for (int i=l;i<=r;i++)
if (!vis[i])
S[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]={};
for (int i=0;i<n;i++)
{
int x=tryCombination(S);
if (x==-1)
ans(d,S);
bool z=(x==i);
int st=0,en=n-1;
while (st!=en)
{
int mid=(st+en)/2;
int f=check(st,mid,S,1);
if (f==-1)
ans(d,S);
unfill(st,mid,S,0);
if (z==0)
{
if (f==i)
en=mid;
else
st=mid+1;
}
else
{
if (f>i)
en=mid;
else
st=mid+1;
}
}
// cout<<st<<' '<<i<<endl;
d[st]=i;
S[st]=z;
vis[st]=1;
}
ans(d,S);
}
