#include "cave.h"
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;
void exploreCave(int N) {
/* ... */
int which_lock[N];
int correct_choice[N];
int buffer[N];
for (int i = 0; i < N; i++)
which_lock[i] = correct_choice[i] = buffer[i] = -1;
for (int iter = 0; iter < N; iter++) {
vector<int> todo;
todo.reserve(N);
for (int i = 0; i < N; i++) {
if (which_lock[i] != -1) {
buffer[i] = correct_choice[i];
} else {
buffer[i] = 0;
todo.push_back(i);
}
assert(buffer[i] != -1);
}
int ret = tryCombination(buffer);
int open_value = 1;
if (ret == -1 or ret > iter) {
// is open
open_value = 0;
}
for (auto u : todo)
buffer[u] = open_value;
int lo = 0, hi = (int)todo.size() - 1;
while (lo < hi) {
int mid = (lo + hi + 1) >> 1;
for (int i = 0; i < mid; i++)
buffer[todo[i]] = (open_value ^ 1);
for (int i = mid; i < (int)todo.size(); i++)
buffer[todo[i]] = open_value;
int ret = tryCombination(buffer);
#ifdef LOCAL
cout << "buffer: ";
for (int i = 0; i < N; i++)
cout << buffer[i] << " ";
cout << "\n";
cout << "ret: " << ret << endl;
#endif
if (ret == -1 or ret > iter)
lo = mid;
else
hi = mid - 1;
}
which_lock[todo[lo]] = iter;
correct_choice[todo[lo]] = open_value;
#ifdef LOCAL
cout << "iter: " << iter << " ";
cout << "open_value: " << open_value << " ";
cout << "which_lock: " << todo[lo] << endl;
#endif
}
answer(correct_choice, which_lock);
}
