#include <list>
#include <vector>
#include <iostream>
#include "cave.h"
// 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 N;
int betterTryCombination(int S[]) {
int a = tryCombination(S);
return a >= 0 ? a : N;
}
int binarySearch(pos start, pos end, int n, int idx, int correctState, int currentState) {
if (n == 1) {
states[*start] = correctState;
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 = betterTryCombination(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_) {
N = N_;
for (int i = 0; i < N; i++) {
left.push_back(i);
}
states.resize(N);
std::vector<int> positions(N, 0);
std::cerr << N << '\n';
for (int idx = 0; idx < N; idx++) {
for (int j : left) {
states[j] = 1;
}
bool correctState = betterTryCombination(states.data()) > idx;
int c = binarySearch(left.begin(), left.end(), N - idx, idx, correctState, 1);
positions[c] = idx;
}
answer(states.data(), positions.data());
}
