#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=5000+10;
int n,tof,vas[maxn],pa[maxn],vasl[maxn];
vector<int>unnow,ers;
int pors(vector<int>ers){
for(int i=0;i<n;i++){
pa[i]=ers[i];
}
int z=tryCombination(pa);
if(z==-1){
z=n+1;
}
return z;
}
vector<int>cand,fake;
void solve(int lev){
if(lev==n){
return ;
}
for(auto x:unnow){
ers[x]=vas[x];
}
for(auto x:cand){
ers[x]=0;
}
int z=pors(ers);
if(z==lev){
tof=1;
}else if(z>lev){
tof=0;
}else{
assert(0);
}
int low=0,high=(int)cand.size(),mid;
while(high-low>1){
mid=(high+low-1)>>1;
for(auto x:unnow){
ers[x]=vas[x];
}
for(int i=low;i<=mid;i++){
ers[cand[i]]=tof;
}
for(int i=mid+1;i<(int)cand.size();i++){
ers[cand[i]]=(1^tof);
}
for(int i=0;i<low;i++){
ers[cand[i]]=(1^tof);
}
z=pors(ers);
if(z==lev){
low=mid+1;
}else if(z>lev){
high=mid+1;
}else{
assert(0);
}
}
vas[cand[low]]=tof;
vasl[cand[low]]=lev;
fake.clear();
for(int i=0;i<(int)cand.size();i++){
if(i!=low){
fake.push_back(cand[i]);
}
}
unnow.push_back(cand[low]);
swap(cand,fake);
return solve(lev+1);
}
void exploreCave(int N) {
n=N;
ers.resize(n);
for(int i=0;i<n;i++){
cand.push_back(i);
}
solve(0);
answer(vas,vasl);
}
