#include "cave.h"
#include <bits/stdc++.h>
#define deb(x) cerr << #x << ": " << x << '\n';
using namespace std;
int N;
const int NMAX = 8192;
int S[NMAX], D[NMAX], test[NMAX];
bool check_state(int first_closed_door, int idx){
if(first_closed_door == -1) return 0;
if(first_closed_door > idx) return 0;
return 1;
}
void exploreCave(int n) {
N = n;
memset(S,-1,sizeof(S));
int t = ceil(log2(N));
int extra = (1 << t);
for(int i = N; i < extra; ++i){
D[i] = i;
S[i] = 0;
}
for(int cur_door = 0; cur_door < n; ++cur_door){
int first_closed_door = tryCombination(test);
/*cerr << "First Combination: ";
for(int it = 0; it < n; ++it)
cerr << test[it] << ' ';*/
bool cur_door_state = check_state(first_closed_door,cur_door); // 0 = open, 1 = closed
//cerr << ", cur_door_state: " << cur_door_state << '\n';
//deb(first_closed_door);
int k = (extra) / 2, start_idx = 0;
string find_switch = "";
for(int i = 0; i < t; ++i){
for(int l=0; l<n; ++l){
if(S[l] == -1)
test[l] = 0;
else
test[l] = S[l];
}
for(int indx = 0; indx < k; ++indx){
if(S[start_idx + indx] == -1)
test[start_idx + indx] = 1;
}
/*cerr << "test: ";
for(int it = 0; it < n; ++it)
cerr << test[it] << ' ';
cerr << '\n';*/
first_closed_door = tryCombination(test);
//deb(first_closed_door);
bool new_cur_door_state = check_state(first_closed_door,cur_door);
//cerr << "cur_door_state, new_cur_door_state: " <<cur_door_state << ' ' << new_cur_door_state << '\n';
if(cur_door_state == new_cur_door_state)
{find_switch += "R"; start_idx += k;}
else
{find_switch += "L";}
k /= 2;
}
//deb(find_switch);
int switch_idx = 0;
int f = extra / 2;
for(char x : find_switch){
if(x == 'R') switch_idx += f;
f /=2;
}
//cerr << "find_switch, switch_idx: " <<find_switch << ' ' << switch_idx << '\n';
D[switch_idx] = cur_door;
if(cur_door_state == 1) S[switch_idx] = 1;
else S[switch_idx] = 0;
/* cerr << "D: ";
for(int it = 0; it < n; ++it)
cerr << D[it] << ' ';
cerr << '\n';
cerr << "S: ";
for(int it = 0; it < n; ++it)
cerr << S[it] << ' ';
cerr << '\n';*/
for(int l=0; l<n; ++l){
if(S[l] == -1)
test[l] = 0;
else
test[l] = S[l];
}
}
/*int klk[4] = {0,0,1,0};
int check = tryCombination(klk);
deb(check);*/
answer(S,D);
}
