#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
// we are looking at door i, find the switch that unlocks it (is in interval [l, r])
void find(int S[], int D[], bool found[], int N, int l, int r, int i, int prev = -2)
{
int x;
if(prev == -2) x = tryCombination(S);
else x = prev;
bool ans1 = 0;
if(x == i)
{
ans1 = 1;
}
if(l == r)
{
if(ans1) S[l] = 1-S[l];
found[l] = 1;
D[l] = i;
return;
}
int m = (l+r)/2;
for(int j = l; j <= m; j++)
{
if(!found[j]) S[j] = 1-S[j];
}
x = tryCombination(S);
bool ans2 = 0;
if(x == i)
{
ans2 = 1;
}
if(ans1 == ans2) find(S, D, found, N, m+1, r, i, x);
else find(S, D, found, N, l, m, i, x);
}
void exploreCave(int N) {
int S[N] = {0};
int D[N] = {0};
bool found[N] = {0};
for(int i = 0; i < N; i++)
{
find(S, D, found, N, 0, N-1, i);
}
answer(S, D);
}
