#include <bits/stdc++.h>
#include "cave.h"
using ll =long long;
ll LINF=1000000000000000000;
int INF=1000000000;
#define pi pair<int,int>
#define pl pair<ll,ll>
#define endl '\n'
#define vi vector<int>
#define vii vector<vector<int>>
#define vl vector<ll>
#define vll vector<vector<ll>>
//#define int ll
using namespace std;
vi correct;
int n;
void sett(int *v,int l,int r,int pos,int* location){
for(int i=0;i<l;i++){
v[i]=!pos;
if(location[i]!=-1)v[i]=correct[i];
}
for(int i=r+1;i<n;i++){v[i]=!pos;if(location[i]!=-1)v[i]=correct[location[i]];}
for(int i=l;i<=r;i++){v[i]=pos;if(location[i]!=-1)v[i]=correct[location[i]];}
}
void exploreCave(int N) {
correct.resize(N,-1);
n=N;
int combination[N];
for(int i=0;i<N;i++)combination[i]=0;
int cave=0;
int location[N];for(int i=0;i<n;i++)location[i]=-1;
int t;
t=tryCombination(combination);
for(int i=0;i<t;i++)correct[i]=0;
correct[t]=1;
while (1){
int l=0,r=N-1;
while(l!=r){
int m=(l+r)/2;
sett(combination,m+1,r,correct[cave],location);
t=tryCombination(combination);
if(t==-1){
answer(combination,location);
return;
}
if(t>cave)l=m+1;
else r=m;
}
location[l]=cave;
for(int i=cave;i<t;i++)correct[i]=combination[i];
correct[t]=!combination[t];
cave++;
}
}
