#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5000;
int n;
int s[N];
int d[N];
vector<bool> vis; // switch que no puedo tocar
int cnt; // numero de switchs que me quedan por tocar
bool abierta;
int find(int i) {
// cual es el switch que corresponde a la puerta i
// cambiar los mid primeros switchs
// si la puerta cambia buscar en los que he cambiado
// si no buscar en los que no he cambiado
int l = 1;
int r = cnt;
int x = tryCombination(s);
abierta = x > i || x == -1;
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];
}
if (tryCombination(s2) > 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 0;
}
void exploreCave(int nn) {
n = nn;
vis.resize(n, 0);
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);
}
