#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
void exploreCave(int N) {
vector<int> correct(N, -1);
vector<int> switches(N, -1);
for(int i = 0; i < N; i++){
if(correct[i] == -1){
int v[N];
for(int j = 0; j < N; j++) v[j] = 0;
for(int j = 0; j < i; j++) v[switches[j]] = correct[j];
int x = tryCombination(v);
if(x == -1){
for(int j = i; j < N; j++) correct[j] = 0;
}else{
for(int j = i; j < x; j++) correct[j] = 0;
correct[x] = 1;
}
}
int lo = 0;
int hi = N - 1;
while(lo < hi){
int mid = (lo + hi) / 2;
int v[N];
for(int j = 0; j < N; j++) v[j] = 1 - correct[i];
for(int j = 0; j < i; j++){
v[switches[j]] = correct[j];
}
for(int j = lo; j <= mid; j++) v[j] = correct[i];
int x = tryCombination(v);
if(x > i || x == -1){
hi = mid;
}else lo = mid + 1;
}
switches[i] = lo;
}
int d[N];
for(int i = 0; i < N; i++){
d[switches[i]] = i;
}
int s[N];
for(int i = 0; i < N; i++){
s[switches[i]] = correct[i];
}
answer(s, d);
}
