#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int N) {
int n = N;
int which_door[N] = {};
int which_switch[] = {};
int open_array[N] = {};
set<int> used;
for(int i = 0; i < n; i++){
// cout << "\n";
// cout << "solving door " << i << "\n";
// find whether this switch is open in pos 0 or 1
int open = 0;
int reach = tryCombination(open_array);
if(reach == i) open = 1;
// cout << reach << "\n";
// cout << "open in pos " << open << "\n";
// cout << "open array is currently ";
// for(auto e : open_array) cout << e << " ";
// cout << "\n";
// binary search for what switch controls door i
int l = 0;
int r = n - 1;
int m = (l + r) / 2;
while(l < r){
int toggles[N] = {};
for(int i = 0; i < n; i++) toggles[i] = open_array[i];
for(int j = l; j <= m; j++){
if(used.find(j) != used.end()) continue;
toggles[j] = 1 ^ open;
}
for(int j = 0; j < l; j++){
if(used.find(j) != used.end()) continue;
toggles[j] = open;
}
for(int j = m + 1; j < N; j++){
if(used.find(j) != used.end()) continue;
toggles[j] = open;
}
// cout <<"trying with toggles ";
// for(auto e : toggles) cout << e << " ";
// cout << "\n";
int range = tryCombination(toggles);
if(range == i) r = m;
else l = m + 1;
m = (l + r) / 2;
}
// cout << "switch is " << l << "\n";
used.insert(l);
which_switch[i] = l;
which_door[l] = i;
open_array[l] = open;
}
answer(open_array, which_door);
}
