| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 356554 | BlancaHM | 동굴 (IOI13_cave) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "cave.h"
#include <iostream>
#include <vector>
using namespace std;
void flip(int & a) {
// flip enciende un interruptor apagado y apaga un interruptor encendido
a = 1 - a;
}
void exploreCave(int N) {
vector<int> direccionFinal(N, -1), conexionFinal(N, -1), direccionInterruptores(N, 0);
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, flip(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, flip(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);
}