#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int f[5000],n,t[5000];
bool provera(int l,int r,int k,bool c)
{
int x[n];
for(int i=0;i<n;i++)
{
if(f[i]!=-1)
{
x[i]=f[i];
continue;
}
if(i>=l&&i<=r) x[i]=c;
else x[i]=!c;
}
int a=tryCombination(x);
if(k==a) return false;
return true;
}
int binarna(int l,int r,int k,bool c)
{
if(l==r) return l;
int s=(l+r)/2;
if(provera(l,s,k,c)) return binarna(l,s,k,c);
return binarna(s+1,r,k,c);
}
void exploreCave(int N)
{
n=N;
fill(f,f+5000,-1);
for(int i=0;i<n;i++)
{
bool x=provera(0,n-1,i,1);
int z=binarna(0,n-1,i,x);
f[z]=x;
t[z]=i;
}
int sol[n],soln[n];
for(int i=0;i<n;i++)
{
sol[i]=f[i];
soln[i]=t[i];
}
answer(sol,soln);
}
