#include <vector>
#include "cave.h"
#include <unordered_set>
using namespace std;
void negatev(vector<int>& comb, const unordered_set<int>& known, int L, int R) {
for(int i = L; i < R; i++) {
if(known.count(i) == 0) {
comb[i] = 1 - comb[i];
}
}
}
void exploreCave(int N) {
vector<int> comb(N, 0);
int current = 0;
vector<int> inter(N, -1);
vector<int> pos(N, -1);
unordered_set<int> known;
known.reserve(N);
int res = tryCombination(comb.data());
bool prev = res != 0;
while(current < N) {
int L = 0, R = N - 1;
while(L != R) {
int mid = (L+R)/2 + 1;
negatev(comb, known, L, mid);
res = tryCombination(comb.data());
bool open = res >= current || res == -1;
if(open != prev) {
R = mid - 1;
} else {
L = mid;
}
prev = open;
}
inter[current] = L;
if(!prev) comb[current] = 1 - comb[current];
pos[current] = comb[current];
prev = res >= current + 1 || res == -1;
known.insert(L);
current++;
}
answer(pos.data(), inter.data());
}
