#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int N) {
int v[N] = {0};
vector<pair<int,int>> known(N,{-1,-1});
for(int i = 1; i <= N; ++i){
int lo = 0, hi = N-1;
int x = tryCombination(v);
if(x == -1)x = N;
x = min(x, i);
while(lo < hi){
int mid = (lo+hi)/2;
for(int j = lo; j <= mid; ++j){
v[j] = (known[j].second != -1 ? known[j].first : v[j]^1);
}
int x2 = tryCombination(v);
if(x2 == -1)x2 = i;
x2 = min(x2, i);
if(x == x2){
lo = mid+1;
}
else hi = mid;
x = x2;
}
known[lo] = {x == i ? v[lo] : v[lo]^1, i-1};
v[lo] = known[lo].first;
}
int out1[N], out2[N];
for(int i = 0; i < N; ++i){
out1[i] = known[i].first;
out2[i] = known[i].second;
}
answer(out1, out2);
}
