#include "cave.h"
#include <iostream>
const int MAXN = 5000;
int p[MAXN], f[MAXN], us[MAXN];
void inverse(int l, int r) {
for (int i = l; i < r; ++i) {
if (!us[i]) f[i] = 1 - f[i];
}
}
void solve(int l, int r, int res) {
if (r - l == 1) {
f[l] = 1 - f[l];
int c = tryCombination(f);
us[l] = 1;
if (c < res && c != -1) {
f[l] = 1 - f[l];
}
return;
}
int s = 0;
for (int i = l; i < r; ++i) {
s += 1 - us[i];
}
if (s == 1) {
for (int i = l; i < r; ++i){
if (!us[i]) {
solve(i, i + 1, res);
return;
}
}
}
int m = l;
int pr = 0;
while (pr < s / 2 && m + 1 < r) {
pr += 1 - us[m];
++m;
}
inverse(l, m);
int c = tryCombination(f);
inverse(l, m);
if (c != res) {
solve(l, m, res);
}
else {
solve(m, r, res);
}
}
void exploreCave(int N) {
for (int i = 0; i < N; ++i) {
f[i] = 0;
us[i] = 0;
}
for (int res = tryCombination(f); res != -1; res = tryCombination(f)) {
if (res == 0) {
inverse(0, N);
continue;
}
solve(0, N, res);
}
for (int i = 0; i < N; ++i) {
f[i] = 1 - f[i];
p[i] = tryCombination(f);
f[i] = 1 - f[i];
}
answer(f, p);
}
