#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
const int nmax=5e3+5;
int qarr[nmax],check[nmax],res[nmax],res1[nmax];
int N;
bool checker(int tmp,int tar)
{
if (tmp==-1) return 1;
return (tmp>tar);
}
void solve(int tar,int l,int r,int known)
{
if (l==r)
{
res[l]=known;
check[l]=1;
res1[l]=tar;
return;
}
memset(qarr,0,sizeof qarr);
int mid=(l+r) >> 1;
for (int i=0;i<N;i++)
{
if (i>=l && i<=mid)
{
qarr[i]=known;
} else
qarr[i]=1^known;
}
for (int i=0;i<N;i++)
{
if (check[i]) qarr[i]=res[i];
}
int ans=tryCombination(qarr);
if (checker(ans,tar))
{
solve(tar,l,mid,known);
} else solve(tar,mid+1,r,known);
}
int findcolor(int tar)
{
memset(qarr,0,sizeof qarr);
for (int i=0;i<N;i++)
{
if (check[i]) qarr[i]=res[i];
}
int ans=tryCombination(qarr);
if (checker(ans,tar)) return 0; else return 1;
}
void exploreCave(int n)
{
N=n;
for (int i=0;i<N;i++)
{
int color= findcolor(i);
solve(i,0,N-1,color);
}
answer(res,res1);
}
