Submission #237352

#	Time	Username	Problem	Language	Result	Execution time	Memory
237352		jam_xd_	Cave (IOI13_cave)	C++17	100 / 100	793 ms	760 KiB

cave

#include "cave.h"
#include "bits/stdc++.h"

using namespace std;


 
void exploreCave(int N) {
	int ggnomas[N]={}, S[N] = {};//inician en 0
	int D[N];
	for(int i=0;i<N;i++){
		// crear el array del si switchs estan encendidos o apagados
		int prb[N];
		for(int j=0;j<N;j++){
			if(ggnomas[j] != 0) prb[j] = S[j];
			else prb[j] = 1;
		}
		int uwu = tryCombination(prb);
		int afirmo = 1;
		if(uwu<=i and uwu!=-1) afirmo = 0;
 
		// Posicion del switch q quiero
		int minimo=0, maximo= N-1;
		int medio;

		//binary search del stack adaptado xd xd
		while(minimo <= maximo){
			medio = (minimo + maximo)/2;
			for(int j=0;j <= medio;j++){
				if(ggnomas[j] != 0) prb[j] = S[j];
				else prb[j] = afirmo;
			}
			for(int k= medio+1;k< N;k++){
				if(ggnomas[k] != 0) prb[k] = S[k];
				else prb[k] = 1 - afirmo;
			}
			uwu = tryCombination(prb);
			if(uwu > i or uwu== -1){
				maximo = medio-1;
			}
			else {
				medio++;
				minimo = medio;
			}
		}
		ggnomas[medio] = 1;
		S[medio] = afirmo;
		D[medio] = i;
	}
		answer(S,D);
}

// >:v

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