#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int n,s[5050],d[5050];
int bs(int cor,int cur){
vector<int> unlinked(0);
for (int i=0;i<n;i++) if (d[i]==-1) unlinked.push_back(i);
int l=0,r=unlinked.size()-1;
while (l!=r){
int m=(l+r)/2;
int findstate[5050];
for (int i=0;i<n;i++){
if (d[i]==-1) findstate[i]=cor;
else findstate[i]=s[i];
}
for (int i=0;i<=m;i++) findstate[unlinked[i]]=cor^1;
int door=tryCombination(findstate);
if (door==-1) door=n;
if (door<=cur) r=m;
else l=m+1;
}
return unlinked[l];
}
void exploreCave(int N){
n=N;
for (int i=0;i<n;i++) d[i]=-1;
for (int i=0;i<n;i++){
int cor,findstate[5050];
for (int j=0;j<n;j++){
if (d[j]==-1) findstate[j]=0;
else findstate[j]=s[j];
}
int door=tryCombination(findstate);
if (door==-1) door=n;
if (door>i) cor=0;
else cor=1;
int sw=bs(cor,i);
s[sw]=cor;
d[sw]=i;
}
answer(s,d);
}
