#include <iostream>
#include <algorithm>
#include <vector>
#include "cave.h"
using namespace std;
const int MAXN = 5e3 + 10;
int s[MAXN], signs[MAXN], d[MAXN], n, current_sign = 2;
//extern int tryCombination(int[]);
int get_next(vector <int>& fixed, vector <int>& rest) {
if (rest.size() == 1) return rest.front();
vector <int> a, b;
int m = rest.size() / 2;
for (int i = 0; i < m; i++) {
a.push_back(rest[i]);
}
for (int i = m; i < rest.size(); i++) {
b.push_back(rest[i]);
}
for (int x : fixed) {
s[x] = signs[x];
}
for (int x : a) {
s[x] = current_sign;
}
for (int x : b) {
s[x] = 1 - current_sign;
}
int len = tryCombination(s);
if (len > fixed.size()) { /// potential error
return get_next(fixed, a);
}
return get_next(fixed, b);
}
void exploreCave(int n) {
vector <int> fixed, rest;
for (int i = 0; i < n; i++) {
rest.push_back(i);
}
for (int i = 0; i < n; i++) {
for (int x : fixed) {
s[x] = signs[x];
}
for (int x : rest) {
s[x] = 0;
}
int len = tryCombination(s);
if (len > fixed.size()) {
current_sign = 0;
} else {
current_sign = 1;
}
int pos = get_next(fixed, rest);
signs[pos] = current_sign;
d[pos] = i;
fixed.push_back(pos);
rest.erase(find(rest.begin(), rest.end(), pos));
}
answer(signs, d);
}
