#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
void exploreCave(int N){
int n = N;
vector<int> whichdoor(n, -1), curpos(n, 0);
vector<pair<int, bool>> switches(n);
for(int i = 0; i < n; i++) switches[i] = {i, false};
for(int cur = 0; cur < n; cur++){
for(int i = 0; i < cur; i++) curpos[switches[i].first] = switches[i].second;
for(int i = cur; i < n; i++) curpos[switches[i].first] = false;
int x = tryCombination(curpos.data());
if(x == -1 || x > cur){
int l = cur, r = n;
while(r - l > 1){
int m = l + (r - l) / 2;
for(int i = cur; i < n; i++) curpos[switches[i].first] = true;
for(int i = m; i < r; i++) curpos[switches[i].first] = false;
int x = tryCombination(curpos.data());
if(x == -1 || x > cur) l = m;
else r = m;
}
swap(switches[cur], switches[l]);
switches[cur].second = false;
whichdoor[switches[cur].first] = cur;
}
else{
int l = cur, r = n;
while(r - l > 1){
int m = l + (r - l) / 2;
for(int i = cur; i < n; i++) curpos[switches[i].first] = false;
for(int i = m; i < r; i++) curpos[switches[i].first] = true;
int x = tryCombination(curpos.data());
if(x == -1 || x > cur) l = m;
else r = m;
}
swap(switches[cur], switches[l]);
switches[cur].second = true;
whichdoor[switches[cur].first] = cur;
}
}
vector<int> correctpos(n);
for(int i = 0; i < n; i++) correctpos[switches[i].first] = switches[i].second;
answer(correctpos.data(), whichdoor.data());
}
