#include "cave.h"
#include <iostream>
using namespace std;
// Subtareas 1, 2 y 3
// void exploreCave(int N) {
// int puerta[N];
// int pos[N];
// bool vis[N];
// for (int i = 0; i < N; i++) {
// pos[i] = 0;
// puerta[i] = -1;
// vis[i] = 0;
// }
// int prev = tryCombination(pos);
// int ans;
// while (prev != -1) {
// for (int i = 0; i < N; i++) {
// if (vis[i]) continue;
// pos[i] = 1;
// ans = tryCombination(pos);
// if (ans > prev || ans == -1) {
// vis[i] = 1;
// prev = ans;
// break;
// }
// if (ans < prev) {
// vis[i] = 1;
// }
// pos[i] = 0;
// }
// }
// for (int i = 0; i < N; i++) {
// pos[i] = (pos[i] + 1) % 2;
// int ans = tryCombination(pos);
// puerta[i] = ans;
// pos[i] = (pos[i] + 1) % 2;
// }
// answer(pos, puerta);
// }
void exploreCave(int N) {
int puerta[N];
int pos[N];
bool vis[N];
for (int i = 0; i < N; i++) {
pos[i] = 0;
puerta[i] = -1;
vis[i] = 0;
}
int prev;
int ans;
int j = 0;
int ini, fin, mid;
while (j < N) {
prev = tryCombination(pos);
ini = 0;
fin = N;
mid = (ini + fin) / 2;
while (fin - ini > 1) {
mid = (ini + fin) / 2;
for (int i = ini; i < mid; i++) {
pos[i] = 1;
}
ans = tryCombination(pos);
for (int i = ini; i < mid; i++) {
if (vis[i]) continue;
pos[i] = 0;
}
if (prev > j) {
if (ans > j || ans == -1) {
ini = mid;
} else {
fin = mid;
}
} else {
if (ans > j || ans == -1) {
fin = mid;
} else {
ini = mid;
}
}
}
mid = (ini + fin) / 2;
vis[j] = 1;
if (prev > j) {
pos[mid] = 0;
} else {
pos[mid] = 1;
}
j++;
}
for (int i = 0; i < N; i++) {
pos[i] = (pos[i] + 1) % 2;
int ans = tryCombination(pos);
puerta[i] = ans;
pos[i] = (pos[i] + 1) % 2;
}
answer(pos, puerta);
}
