#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include "cave.h"
using namespace std;
const int N = 5e3 + 7;
int a[N];
int use[N];
int b[N];
int wh[N];
int an[N];
int con[N];
void pri(int n, int ma[]) {
for (int i = 0; i < n; ++i) {
cout << ma[i] << " ";
}
cout << endl;
}
void pr(int n, int ma[],int an) {
pri(n, ma);
cout << "ANS=" <<an;
cout << endl;
}
void exploreCave(int N) {
for (int i = 0; i < N; ++i) {
int n = 0;
for (int j = 0; j < N; ++j) {
if (use[j])continue;
a[n++] = j;
}
int st = 0;
bool org = 0;
for (int j = 0; j < N; ++j) {
if (use[j])b[j] = wh[j];
else b[j] = 0;
}
int ok = tryCombination(b);
if (ok==i)org = 1;
for (int j=0; j < N; ++j) {
if (use[j])continue;
else
b[j] = org^1;
}
int l = 0, r = n - 1;
while (l <= r) {
st = (l + r) / 2;
if (l == r)break;
for (int j = l; j <= st; ++j) {
b[a[j]] = org;
}
ok = tryCombination(b);
for (int j = l; j <= st; ++j)b[a[j]] = org^1;
if (ok == i) {
l = st + 1;
st = l;
}
else {
r = st;
}
}
con[i] = a[st];
wh[a[st]] = org;
use[a[st]] = true;
b[a[st]] = org;
}
for (int i = 0; i < N; ++i) {
an[con[i]] = i;
}
answer(wh, an);
}
