// ~ Be Name Khoda ~ //
#include "cave.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 5e3 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 1e18;
int n, ask[maxn5], mat[maxn5];
int cor[maxn5], av[maxn5];
bool det[maxn5];
inline int check(int l, int r, int ty){
for(int i = 0; i < n; i++){
if(det[i])
ask[i] = cor[i];
else
ask[i] = (l > i || i >= r) ^ ty;
}
return tryCombination(ask);
}
void exploreCave(int N) {
n = N;
memset(det, false, sizeof det);
for(int i = 0; i < n; i++){
int pt = 0;
for(int j = 0; j < n; j++){
if(!det[j]){
av[pt++] = j;
ask[j] = true;
}
else
ask[j] = cor[j];
}
av[pt] = maxn5;
int last = tryCombination(ask);
bool ty = (last != i);
int lo = 0, hi = pt;
while(hi - lo > 1){
int mid = (lo + hi) >> 1;
if(i != check(av[lo], av[mid], ty))
hi = mid;
else
lo = mid;
}
cor[av[lo]] = ty;
mat[av[lo]] = i;
det[av[lo]] = true;
//cout << "found " << i << ' ' << ty << ' ' << lo << ' ' << hi << ' ' << pt << ' ' << av[lo] << endl;
}
answer(cor, mat);
}
