#include <list>
#include <vector>
extern "C" {
int tryCombination(int S[/* who needs type safety */]);
void answer(int S[], int D[]);
void exploreCave(int N);
}
std::vector<int> states;
using pos = std::list<int>::iterator;
std::list<int> left;
int binarySearch(pos start, pos end, int n, int idx, int correctState, int currentState) {
if (n == 1) {
int c = *start;
left.erase(start);
return c;
}
int m = n / 2;
auto mid = start;
for (int i = 0; i < m; i++, mid++) {
states[*mid] = !currentState;
}
bool open = tryCombination(states.data()) > idx;
if (open == (currentState == correctState)) {
return binarySearch(mid, end, n - m, idx, correctState, currentState);
} else {
return binarySearch(start, mid, m, idx, correctState, !currentState);
}
}
void exploreCave(int N) {
for (int i = 0; i < N; i++) {
left.push_back(i);
}
states.resize(N);
std::vector<int> positions(N, 0);
for (int idx = 0; idx < N; idx++) {
for (int j : left) {
states[j] = 1;
}
bool correctState = tryCombination(states.data()) > idx;
int c = binarySearch(left.begin(), left.end(), N - idx, idx, correctState, 1);
positions[c] = idx;
}
answer(states.data(), positions.data());
}
