#include <bits/stdc++.h>
#include "cave.h"
#define pb push_back
#define pii pair<int, int>
#define nyan "(=^･ω･^=)"
#define read_input freopen("in.txt","r", stdin)
#define print_output freopen("out.txt","w", stdout)
typedef long long ll;
typedef long double ld;
using namespace std;
int n;
void filter(int *a, int *b) {
for(int i = 0; i < n; i++)
if(b[i] != -1) a[i] = b[i];
}
void flip(int *a, int l, int r) {
for(int i = l; i <= r; i++) a[i] ^= 1;
}
void exploreCave(int N) {
n = N;
//tryCombination(a);
int a[N], b[N], D[N];
memset(b, -1, sizeof b);
for(int i = 0; i < N-1; i++) {
int t1 = i+1;
memset(a, 0, sizeof a);
filter(a, b);
int check = tryCombination(a);
int x = 0;
if(check != -1 && check < t1) { // i'th gate does not open with 0
flip(a, 0, n-1);
filter(a, b);
x = 1;
}
memset(a, 0, sizeof a);
if(x) flip(a, 0, n-1);
int lo = 0, hi = n-1;
while(lo < hi) {
int mid = lo + hi >> 1;
flip(a, lo, mid); filter(a, b);
int t2 = tryCombination(a);
if(t2 >= t1 || t2 == -1) lo = mid+1;
else {
hi = mid;
flip(a, lo, mid);
}
}
b[lo] = a[lo]; // correct direction of switch of i'th door
D[lo] = i;
}
int hole;
for(int i = 0; i < n; i++) if(b[i] == -1) hole = i;
memset(a, 0, sizeof a); filter(a, b);
int check = tryCombination(a);
if(check == -1) b[hole] = 0;
else b[hole] = 1;
D[hole] = n-1;
/*for(int i = 0; i < n; i++) {
b[i] ^= 1;
D[i] = tryCombination(b);
b[i] ^= 1;
}*/
answer(b, D);
}
