#include "cave.h"
#include <vector>
#include <iostream>
#include <string.h>
void exploreCave(int N) {
using namespace std;
auto guess = [&](vector<int>& g) {
int s[N];
for (int i = 0; i < N; i++) {
s[i] = g[i];
}
int res = tryCombination(s);
return (res == -1 ? 1e9 : res);
};
vector<int> ans(N), where(N), fix(N);
auto build = [&](int l, int r) {
vector<int> g = ans;
for (int i = l; i <= r; i++) {
if (fix[i]) g[i] = ans[i] ^ 1;
}
return g;
};
int score = guess(ans);
for (int i = 0; i < N; i++) {
if (score <= i) {
int l = 0, r = N - 1, loc = -1;
while (l <= r) {
int m = l + (r - l) / 2;
vector<int> g = build(l, m);
int score = guess(g);
if (score >= i) {
loc = m;
r = m - 1;
} else {
l = m + 1;
}
}
fix[loc] ^= ans[loc];
ans[loc] ^= ans[loc];
where[i] = loc;
} else {
int l = 0, r = N - 1, loc = -1;
while (l <= r) {
int m = l + (r - l) / 2;
vector<int> g = build(l, m);
int score = guess(g);
if (score < i) {
loc = m;
r = m - 1;
} else {
l = m + 1;
}
}
fix[loc] ^= ans[loc];
ans[loc] ^= ans[loc];
where[i] = loc;
}
}
int a[N], b[N];
for (int i = 0; i < N; i++) {
a[i] = ans[i];
b[i] = where[i];
}
answer(a, b);
}
