#include "cave.h"
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))
using namespace std;
#define wiwihorz
#ifdef wiwihorz
#define print(a...) kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) {while(L < R) cerr << *L << " \n"[next(L) == R], ++L; }
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...); }
#else
#define print(...) 0
#define vprint(...) 0
#endif
int cur[5001], a[5001], b[5001], s[5001], d[5001], n;
void make_combination(int x, int y, bool type) {
rep(i, 0, y) cur[i] = type;
rep(i, y + 1, n - 1) cur[i] = !type;
rep(i, 0, x - 1) cur[a[i]] = b[i];
return;
}
void exploreCave(int N) {
n = N;
rep(i, 0, n - 1) {
make_combination(i, n - 1, 0);
bool type = 1; int l = -1, r = n - 1;
if(tryCombination(cur) > i) type = 0;
while(r - l > 1) {
int mid = (l + r) / 2;
make_combination(i, mid, type);
int ans = tryCombination(cur);
if(ans > i || ans == -1) r = mid;
else l = mid;
}
a[i] = r, b[i] = type;
}
rep(i, 0, n - 1) {
s[a[i]] = b[i];
d[a[i]] = i;
}
answer(s, d);
return;
}
