#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);
bool cur_door_state = check_state(first_closed_door,cur_door); // 0 = open, 1 = closed
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;
}
first_closed_door = tryCombination(test);
bool new_cur_door_state = check_state(first_closed_door,cur_door);
if(cur_door_state == new_cur_door_state)
{find_switch += "R"; start_idx += k;}
else
{find_switch += "L";}
k /= 2;
}
int switch_idx = 0;
int f = extra / 2;
for(char x : find_switch){
if(x == 'R') switch_idx += f;
f /=2;
}
D[switch_idx] = cur_door;
if(cur_door_state == 1) S[switch_idx] = 1;
else S[switch_idx] = 0;
for(int l=0; l<n; ++l){
if(S[l] == -1)
test[l] = 0;
else
test[l] = S[l];
}
}
answer(S,D);
}
