#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template<typename T> using vec = vector<T>;
constexpr int tree_length = 1<<20;
#define F(l, r) for(int i = (int)l; i < (int)r; i++)
int INF = 1e9 + 1000;
vec<int> door, dir_to_open_switch;
int n;
int help = 0;
void find_switch_to_door(int x){
auto a = new int[n];
F(0, n){
a[i] = dir_to_open_switch[i] == -1 ? 0 : dir_to_open_switch[i];
}
int depth = tryCombination(a);
help++;
auto change_interval = [&](int L, int R){
F(L, R+1){
if(dir_to_open_switch[i] == -1) a[i] = !a[i];
}
help++;
return tryCombination(a);
};
// try to switch the first half
int L = 0, R = n-1;
while(L != R){
int M = (L+R)/2;
int new_depth = change_interval(L, M);
bool change = (new_depth == x && depth != x) || (new_depth != x && depth == x);
depth = new_depth;
if(change){
// they are on interval L, M;
R = M;
} else{
L = M+1;
}
}
door[x] = L;
// cout << "door " << x << " is connected to switch: " << L << '\n';
dir_to_open_switch[L] = (depth == x ? !a[L] : a[L]); // if depth = x => switch L closes x door
}
void exploreCave(int N){
n = N;
// determine the first switch: binsearch: change a half of switches, if the depth changed to 1 or from 1 => 1 is in the first half, else it's in the other. At the end switch off 1 and look for 2
door.assign(n, -1);
dir_to_open_switch.assign(n, -1);
F(0, n){
find_switch_to_door(i);
}
auto S = new int[n];
auto D = new int[n];
for (int i = 0; i < n; i++){
D[door[i]] = i;
S[door[i]] = dir_to_open_switch[door[i]];
}
// cout << help << " ok\n???\n";
// if(help > 70'000) exit(1);
answer(S, D);
}
