#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
int n, *s, *t, last;
void flip(int start, int end){
for(int i = start; i <= end; i++){
if(t[i] != -1) continue;
s[i] = 1 - s[i];
}
}
int bs(int j){
int lo = 0, hi = n - 1, mid, res = -1;
while(lo <= hi){
mid = (lo + hi)/2;
flip(mid, hi);
int next = tryCombination(s);
// cerr << mid << " " << hi << '\n';
// for(int i = 0; i < n; i++){
// cerr << s[i] << ' ';
// }
// cerr << '\n';
// cerr << " " << last << " " << next << '\n';
if(next != last && (next == j || last == j)){
lo = mid + 1;
res = mid;
}
else {
hi = mid - 1;
}
last = next;
}
return res;
}
void exploreCave(int N) {
n = N;
s = new int[n];
t = new int[n];
//Initializing
for(int i = 0; i < n; i++){
t[i] = -1;
s[i] = 0;
}
int j = 0;
while(j < n){
last = tryCombination(s);
int i = bs(j);
t[i] = j;
if(last == j) s[i] = 1 - s[i];
j++;
}
answer(s, t);
}
