#define task ""
#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#include "cave.h"
constexpr int N = 5e3 + 5;
constexpr int Inf = 1e9 + 7;
int a[N], s[N], d[N];
int m, nn;
void Fill(int l, int r, int v)
{
for (int i = l; i <= r; ++i)
s[a[i]] = v;
}
int Guess(int l, int r, int v)
{
Fill(l, r, v);
int x = tryCombination(s);
return (x == -1 ? Inf : x);
}
int Get(int l, int r, const int &v, const int &i)
{
Fill(l, r, v);
while (l != r)
{
if (Guess(l, (l + r) / 2, !v) == i)
{
Fill(l, r, v);
r = (l + r) / 2;
}
else
{
Fill(l, r, v);
l = (l + r) / 2 + 1;
}
}
return l;
}
void exploreCave(int n)
{
m = n;
for (int i = 0; i < n; ++i)
a[i] = i;
for (int i = 0; i < n; ++i)
{
if (Guess(0, m - 1, 1) > i)
{
int tmp = Get(0, m - 1, 1, i);
s[a[tmp]] = 1;
d[a[tmp]] = i;
a[tmp] = a[--m];
}
else
{
int tmp = Get(0, m - 1, 0, i);
s[a[tmp]] = 0;
d[a[tmp]] = i;
a[tmp] = a[--m];
}
}
answer(s, d);
}
