#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
#define all(x) (x).begin(), (x).end()
#define isz(x) int(x.size())
using vi = vector<int>;
using ll = long long;
using pii = pair<int, int>;
const int inf = 1e9;
const int sz = 2e5;
vi s, d;
int* convert(vector<int>& v) {
return v.data();
}
int x;
int ask(vi s) {
int S[isz(s)];
for (int i = 0; i < isz(s); i++) S[i] = s[i];
return tryCombination(S);
}
int solve(int l, int r, int c) {
if (l == r) return l;
int mid = (l + r) / 2;
for (int i = l; i <= mid; i++) {
if (d[i] != inf) continue;
s[i] = c;
}
for (int i = mid + 1; i <= r; i++) {
if (d[i] != inf) continue;
s[i] = (c ^ 1);
}
// cout << "l and r : " << l << " " << r << endl;
// for (int i = 0; i < isz(s); i++) cout << s[i] << " ";
// cout << endl;
int sm = ask(s);
// cout << "aks(s) : " << sm << '\n';
if (sm > x || sm == -1) {
return solve(l, mid, c);
}
else
return solve(mid + 1, r, c);
}
void exploreCave(int N) {
int n = N;
d.resize(n, inf);
s.assign(n, 0);
while (ask(s) != -1) {
int idx = ask(s);
x = idx;
vi S = s;
auto val = solve(0, n - 1, 1);
s = S;
s[val] = 1;
d[val] = idx;
}
s.assign(n, 1);
while (ask(s) != -1) {
int idx = ask(s);
x = idx;
vi S = s;
auto val = solve(0, n - 1, 0);
s = S;
s[val] = 0;
d[val] = idx;
}
answer(convert(s), convert(d));
}
