#include "cave.h"
#include <iostream>
#include <cstring>
using namespace std;
int n;
void makeCombination(int s, int m, int S[], int S_try[]) {
for (int i = 0; i <= m; i++) {
S_try[i] = (S[i] == -1 ? s : S[i]);
}
for (int i = m + 1; i < n; i++) {
S_try[i] = (S[i] == -1 ? !s : S[i]);
}
// cout << "----" << endl;
// for (int i = 0; i < n; i++) {
// cout << S_try[i] << ' ';
// }
// cout << endl;
// cout << "----" << endl;
}
bool isOpen(int door, int S_try[]) {
int reached = tryCombination(S_try);
if (reached == -1) reached = n;
return door < reached;
}
int openStateOf(int door, int S[], int S_try[]) {
makeCombination(1, n - 1, S, S_try);
return isOpen(door, S_try);
}
int switchOf(int door, int s, int S[], int S_try[]) {
int l = 0, r = n - 1;
while (r - l > 1) {
int m = (l + r) / 2;
makeCombination(s, m, S, S_try);
if (isOpen(door, S_try)) r = m;
else l = m + 1;
}
if (r == l) return l;
makeCombination(s, l, S, S_try);
if (isOpen(door, S_try)) return l;
return r;
}
void exploreCave(int N) {
n = N;
int S[n], D[n], S_try[n];
memset(S, -1, sizeof S);
memset(D, -1, sizeof D);
for (int i = 0; i < n; i++) {
int s = openStateOf(i, S, S_try);
int d = switchOf(i, s, S, S_try);
S[d] = s;
D[d] = i;
}
answer(S, D);
}
