#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+1)/2;
int findstate[5050];
for (int i=0;i<n;i++){
if (d[i]==-1) findstate[i]=0;
else findstate[i]=s[i];
}
for (int i=0;i<m;i++) findstate[unlinked[i]]=1;
int door=tryCombination(findstate);
if (door<cur) r=m-1;
else l=m;
}
return 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>i) cor=0;
else cor=1;
int sw=bs(cor,i);
d[sw]=i;
s[sw]=cor;
}
answer(s,d);
}
