#include "cave.h"
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
void flip(int & a) {
// flip enciende un interruptor apagado y apaga un interruptor encendido
a = 1 - a;
}
void exploreCave(int N) {
int direccionFinal[N], conexionFinal[N], direccionInterruptores[N];
memset(direccionFinal, -1, sizeof(direccionFinal)); // asignamos -1 a todas las posiciones
memset(conexionFinal, -1, sizeof(conexionFinal)); // asignamos -1 a todas las posiciones
memset(direccionInterruptores, 0, sizeof(direccionInterruptores)); // asignamos 0 a todas las posiciones
int puertasAbiertas1, puertasAbiertas2, lo, hi, mid;
if (N == 1) {
// solo hay una puerta -> hacemos una llamada para ver la dirección del interruptor
puertasAbiertas1 = tryCombination(direccionInterruptores);
if (puertasAbiertas1 == 0) direccionFinal[0] = 1;
else direccionFinal[0] = 0;
conexionFinal[0] = 0;
answer(direccionFinal, conexionFinal);
return;
}
pair<int, int> respuesta = make_pair(0, 0);
for (int i = 0; i < N; i++) {
// primero, averiguaremos la dirección del interruptor que abre la puerta i
puertasAbiertas1 = tryCombination(direccionInterruptores);
// nos aseguramos de que la variable guarde el número de puertas abiertas
if (puertasAbiertas1 == -1)
puertasAbiertas1 = N;
// hacemos bisección para encontrar qué interruptor abre la i'ésima puerta
lo = 0;
hi = N-1;
while(lo < hi) {
mid = lo + (hi-lo)/2;
for (int j = lo; j <= mid; j++) {
// alteramos la dirección de la primera mitad de interruptores cuya dirección final no es conocida
if (conexionFinal[j] == -1)
flip(direccionInterruptores[j]);
}
puertasAbiertas2 = tryCombination(direccionInterruptores);
for (int j = lo; j <= mid; j++) {
// los devolvemos a su estado original tras la prueba
if (conexionFinal[j] == -1)
flip(direccionInterruptores[j]);
}
// nos aseguramos de que la variable guarde el número de puertas abiertas
if (puertasAbiertas2 == -1)
puertasAbiertas2 = N;
if (puertasAbiertas2 > i) {
// la puerta i'ésima se abrió con la nueva combinación
if (puertasAbiertas1 <= i) {
// la puerta i'ésima no se abrió con la vieja combinación
// el interruptor está en la primera mitad
// hay que cambiar su dirección
hi = mid;
respuesta = make_pair(mid, 1-direccionInterruptores[mid]);
} else {
// la puerta i'ésima se abrió con la vieja combinación
// el interruptor está en la segunda mitad
// no hay que cambiar la dirección
lo = mid+1;
respuesta = make_pair(mid+1, direccionInterruptores[mid+1]);
}
} else {
// la puerta i'ésima no abrió con la nueva combinación
if (puertasAbiertas1 <= i) {
// la puerta i'ésima se abrió con la vieja combinación
// el interruptor está en la primera mitad
// hay que cambiar su dirección
lo = mid+1;
respuesta = make_pair(mid+1, 1-direccionInterruptores[mid+1]);
}
else {
// la puerta i'ésima no se abrió con la vieja combinación
// el interruptor está en la segunda mitad
// no hay que cambiar la dirección
hi = mid;
respuesta = make_pair(mid, direccionInterruptores[mid]);
}
}
}
conexionFinal[respuesta.first] = i;
direccionFinal[respuesta.first] = respuesta.second;
direccionInterruptores[respuesta.first] = respuesta.second;
}
answer(direccionFinal, conexionFinal);
}
