#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>;
#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];
vec<int> a(n);
F(0, n){
a[i] = dir_to_open_switch[i] == -1 ? 0 : dir_to_open_switch[i];
}
int depth = tryCombination(a.data());
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.data());
};
// 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;
door.assign(n, -1);
dir_to_open_switch.assign(n, -1);
F(0, n){
find_switch_to_door(i);
}
vec<int> S(n);
vec<int> D(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.data(), D.data());
}
