#include "bits/stdc++.h"
#include "cave.h"
using namespace std;
const int maxn = 5005;
int a[maxn], mark[maxn], b[maxn], match[maxn];
void exploreCave(int N) {
for (int door = 0; door < N; ++door) {
for (int i = 0; i < N; ++i) {
if (mark[i]) b[i] = a[i];
else b[i] = 0;
}
int res = tryCombination(b);
if (res == -1) res = N;
//cerr << res << '\n';
const auto ask = [&](int pivot, int v) {
for (int i = 0; i < N; ++i) {
if (mark[i]) b[i] = a[i];
else b[i] = 0;
}
for (int i = 0; i <= pivot; ++i) {
if (not mark[i])
b[i] = (v ^ 1);
}
for (int i = pivot + 1; i < N; ++i) {
if (not mark[i]) b[i] = v;
}
int r = tryCombination(b);
// cerr << "return " << r << '\n';
if (r == -1) r = N;
return (r > door);
};
int l = 0, r = N - 1, mid;
while (l <= r) {
mid = (l + r) / 2;
if (not ask(mid, (res <= door))) r = mid - 1;
else l = mid + 1;
}
//cerr << "pos " << r << '\n';
if (door == 2) {
for (int i = 0; i < N; ++i) {
// cerr << "check " << i << ' ' << ask(i, (res <= door)) << '\n';
}
}
if (res > door) {
/// val = 0
a[l] = 0;
mark[l] = 1; match[l] = door;
} else {
/// val = 1
a[l] = 1;
mark[l] = 1; match[l] = door;
}
}
answer(a, match);
}
#ifdef LOCAL
int main() {
init();
exploreCave(N);
}
#endif
