#include <bits/stdc++.h>
#include"cave.h"
using namespace std;
/** |||||||||||||||||||||||||||||||| SOLUTION |||||||||||||||||||||||||||||||| **/
int n, pos[5024], d[5024], arr[5024];
bitset<5024>done;
void div(int v, int l, int r, int col) {
if(l==r) {
done[l]=true;
pos[l]=col; d[l]=v;
return;
}
int mid=(l+r)/2;
for(int i=0;i<n;i++) {
if(l<=i&&mid>=i) arr[i]=col;
else arr[i]=1^col;
}
for(int i=0;i<n;i++)
if(done[i]) arr[i]=pos[i];
int a=tryCombination(arr);
if(a==-1||a>v) div(v, l, mid, col);
else div(v, mid+1, r, col);
}
int solve(int i)
{
for(int l=0;l<n;l++) arr[l]=0;
for(int l=0;l<n;l++)
if(done[l]) arr[l]=pos[l];
int a=tryCombination(arr);
if(a==-1||a>i) return 0;
else return 1;
}
void exploreCave(int N) {
n=N;
for(int l=0;l<n;l++) {
int a=solve(l);
div(l, 0, n-1, a);
}
answer(pos, d);
}
