제출 #356566

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
356566		BlancaHM	동굴 (IOI13_cave)	C++14	100 / 100	386 ms	636 KiB

cave

#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);
}

• Subtask 1: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24