#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
void exploreCave(int n) {
/* ... */
int cur = 0;
int swit[n];
int ans[n];
for (int i = 0;i<n;++i)swit[i] = -1;
while(cur<n){
function<int(int,int,int)> solve = [&](int val,int left ,int right){
if (right - left<1)return left;
int mid = (left + right)>>1;
int temp[n];
for (int i = 0;i<left;++i){
if (swit[i]==-1){
temp[i] = val^1;
}
else temp[i] = ans[i];
}
for (int i = left;i<=mid;++i){
if (swit[i]==-1){
temp[i] = val;
}
else{
temp[i] = ans[i];
}
}
for (int i = mid+1;i<n;++i){
if (swit[i]==-1){
temp[i] = val^1;
}
else{
temp[i] = ans[i];
}
}
int anss;
int a = tryCombination(temp);
if (a>cur || a==-1){
anss = solve(val,left,mid);
}
else anss = solve(val,mid+1,right);
return anss;
};
int val = -1;
for (int j = 0;j<2;++j){
int temp[n] = {0};
for (int i = 0;i<n;++i){
if (swit[i]==-1){
temp[i] = j;
}
else temp[i] = ans[i];
}
int a = tryCombination(temp);
if (a>cur||a==-1){
val = j;
break;
}
}
int left = solve(val,0,n-1);
// cout<<left<<" "<<val<<" "<<cur<<'\n';
swit[left] = cur;
ans[left] = val;
//cout<<left<<" "<<cur<<'\n';
++cur;
}
answer(ans,swit);
}
