#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5000 + 5;
int conn[MAX_N], optimal[MAX_N];
int estado[MAX_N], as[MAX_N];
void exploreCave(int n) {
auto ask = [&](const vector<int> &arr) {
for (int i = 0; i < n; i++) {
as[i] = arr[i];
}
int res = tryCombination(as);
return (res == -1 ? n : res);
};
vector<int> sw_state(n, -1);
vector<int> sw_conn(n, -1);
vector<int> state(n, 0);
int current_door = ask(state);
vector<int> valid_switch(n);
iota(valid_switch.begin(), valid_switch.end(), 0);
for (int porta_atual = 0; porta_atual < n; porta_atual++) {
int lo = 0;
int hi = (int) valid_switch.size();
while(lo < hi) {
const int mid = lo + (hi - lo) / 2 + 1;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
arr[i] = estado[i];
}
for (int i = 0; i < mid; i++) {
const int s_i = valid_switch[i];
arr[s_i] = 1;
}
int nxt_door = ask(arr);
if (current_door > porta_atual) {
if (nxt_door == porta_atual) {
hi = mid - 1;
} else {
lo = mid;
}
} else {
if (nxt_door > porta_atual) {
hi = mid - 1;
} else {
lo = mid;
}
}
}
sw_conn[porta_atual] = valid_switch[hi];
sw_state[porta_atual] = (current_door > porta_atual ? 0 : 1);
valid_switch.erase(find(valid_switch.begin(), valid_switch.end(), valid_switch[hi]));
estado[sw_conn[porta_atual]] = sw_state[porta_atual];
int res = tryCombination(estado);
current_door = (res == -1 ? n : res);
// cout << "BOTAO DA PORTA: " << porta_atual << ' ' << sw_conn[porta_atual] << ' ' << sw_state[porta_atual] << '\n';
conn[sw_conn[porta_atual]] = porta_atual;
optimal[sw_conn[porta_atual]] = sw_state[porta_atual];
}
answer(optimal, conn);
}
