#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define sp <<" "<<
#define endl "\n"
void exploreCave(int N) {
int flip[N], conn[N], attempt[N], bit[N];
memset(flip, -1, sizeof(flip));
memset(bit, -1, sizeof(bit));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (flip[j] == -1) attempt[j] = 0;
else attempt[j] = flip[j];
}
int query = tryCombination(attempt);
bit[i] = (query > i or query == -1 ? 0 : 1);
for (int j = 0; j < N; j++) {
if (flip[j] == -1) attempt[j] = 1 - bit[i];
else attempt[j] = flip[j];
}
int lo = -1, hi = N-1;
while (hi - lo > 1) {
int mid = (lo+hi) / 2;
for (int j = lo+1; j <= mid; j++) {
if (flip[j] != -1) continue;
attempt[j] = bit[i];
}
query = tryCombination(attempt);
for (int j = lo+1; j <= mid; j++) {
if (flip[j] != -1) continue;
attempt[j] = 1 - bit[i];
}
if (query > i or query == -1) {
hi = mid;
} else {
lo = mid;
}
}
flip[hi] = bit[i];
conn[hi] = i;
}
answer(flip, conn);
}
