#include "cave.h"
#include <vector>
using namespace std;
int tmp, s[5006], t[5006];
void exploreCave(int n) {
vector<int> empty_list;
for (int i = 0; i < n; i++) empty_list.push_back(i);
for (int i = 0; i < n; i++) {
for (int i = 0; i < (int)empty_list.size(); i++) s[empty_list[i]] = 0;
tmp = tryCombination(s);
bool zero = (tmp == -1) || (tmp >= i + 1);
if (zero) {
int l = 0, r = (int)empty_list.size() - 1;
while (l < r) {
int m = (l + r) / 2;
for (int i = 0; i <= m; i++) s[empty_list[i]] = 0;
for (int i = m + 1; i <= r; i++) s[empty_list[i]] = 1;
tmp = tryCombination(s);
if (tmp == -1 || tmp >= i + 1) r = m;
else l = m + 1;
}
s[empty_list[l]] = 0;
t[empty_list[l]] = i;
empty_list.erase(empty_list.begin() + l);
} else {
int l = 0, r = (int)empty_list.size() - 1;
while (l < r) {
int m = (l + r) / 2;
for (int i = 0; i <= m; i++) s[empty_list[i]] = 1;
for (int i = m + 1; i <= r; i++) s[empty_list[i]] = 0;
tmp = tryCombination(s);
if (tmp == -1 || tmp >= i + 1) r = m;
else l = m + 1;
}
s[empty_list[l]] = 1;
t[empty_list[l]] = i;
empty_list.erase(empty_list.begin() + l);
}
}
answer(s, t);
}
