#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
int ans[5005], anscor[5005], at[5005], cor[5005];
vector<int> a;
void find(int i, int n) {
int c = 0, v;
int s[n];
for (int j = 0; j < i; j++) {
s[at[j]] = cor[j];
}
for (int j : a) {
s[j] = c;
}
v = tryCombination(s);
if (v <= i && v != -1) {
c = 1;
}
for (int j : a) {
s[j] = c^1;
}
int l = 0, r = a.size()-1;
while(l < r) {
int m = (l+r)/2;
for (int j = l; j <= m; j++) {
s[a[j]] = c;
}
v = tryCombination(s);
for (int j = l; j <= m; j++) {
s[a[j]] = c^1;
}
if (v <= i && v != -1) {
l = m+1;
} else {
r = m;
}
}
at[i] = a[l];
cor[i] = c;
ans[a[l]] = i;
anscor[a[l]] = c;
a.erase(a.begin()+l);
}
void exploreCave(int n) {
for (int i = 0; i < n; i++) {
a.push_back(i);
}
for (int i = 0; i < n; i++) {
find(i, n);
}
answer(anscor, ans);
}
