#include "cave.h"
#include <set>
#include <vector>
int S[5000];
int D[5000];
template <class T>
using Vec = std::vector<T>;
void exploreCave(int N) {
const auto query = [&] {
const auto ret = tryCombination(S);
return ret == -1 ? N : ret;
};
std::set<int> remain;
for (int i = 0; i < N; ++i) {
remain.insert(i);
}
for (int d = 0; d < N; ++d) {
// Which switch is connected to the door 'd' ?
for (const auto x: remain) {
S[x] = 0;
}
const auto allZero = query();
Vec<int> cur(remain.begin(), remain.end());
while (cur.size() > 1) {
Vec<int> next;
next.reserve((cur.size() + 1) / 2);
while (cur.size() > next.size()) {
next.push_back(cur.back());
cur.pop_back();
}
for (const auto x: cur) {
S[x] = 1;
}
const auto tmp = query();
for (const auto x: cur) {
S[x] = 0;
}
if ((allZero == d) == (tmp == d)) {
cur = std::move(next);
}
}
const auto i = cur.front();
remain.erase(i);
D[i] = d;
S[i] = (allZero == d ? 1 : 0);
}
answer(S, D);
}
