#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5000;
int n;
int s[N];
int d[N];
bool vis[N]; // switch que no puedo tocar
int cnt; // numero de switchs que me quedan por tocar
int mxAbierta;
bool abierta;
int find(int i) {
// cual es el switch que corresponde a la puerta i
// cambiar los [l - mid] switchs
// si la puerta cambia buscar en los que he cambiado
// si no buscar en los que no he cambiado
if (mxAbierta <= i) mxAbierta = tryCombination(s);
if (mxAbierta == -1) mxAbierta = n;
abierta = mxAbierta > i;
int l = 1;
int r = cnt;
while (l < r) {
int mid = (l+r)/2;
int s2[N];
for (int j = 0; j < n; j++) {
s2[j] = s[j];
}
int temp = 0;
for (int j = 0; j < n && temp < mid; j++) {
if (vis[j]) continue;
temp++;
if (temp >= l) s2[j] = !s2[j];
}
int x = tryCombination(s2);
if (x == -1) x = n;
if (x > i) {
if (!abierta) {
r = mid;
}
else {
l = mid+1;
}
}
else {
if (abierta) {
r = mid;
}
else {
l = mid+1;
}
}
}
int temp = 0;
for (int j = 0; j < n; j++) {
if (vis[j]) continue;
temp++;
if (temp == l) return j;
}
return rand() % n; // nunca llego
}
void exploreCave(int nn) {
n = nn;
cnt = n;
for (int i = 0; i < n; i++) {
int x = find(i);
d[x] = i;
if (!abierta) {
s[x] = !s[x];
}
vis[x] = 1;
cnt--;
}
answer(s, d);
}
