#include "cave.h"
#include <cassert>
#include <cstring>
#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;
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;
memset(cur, 0, sizeof(cur));
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(s, 0, sizeof(s));
memset(d, 0, sizeof(d));
rep(i, 0, n - 1) {
make_combination(i, n - 1, 0);
bool type = 0; int l = -1, r = n - 1;
int xx = tryCombination(cur);
if(tryCombination(cur) != i) type = 1;
while(r - l > 1) {
int mid = (l + r) / 2;
make_combination(i, mid, type);
int ans = tryCombination(cur);
if(ans != i) 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;
}
