Submission #212994

#	Time	Username	Problem	Language	Result	Execution time	Memory
212994		bigg	Cave (IOI13_cave)	C++14	100 / 100	508 ms	588 KiB

cave

#include "cave.h"

int marc[5123];
int n, R[5123], ans[5123]; 

void flip(int i, int j){
	for(; i <= j; i++)
		if(!marc[i])
			R[i] = !R[i];
	
}


void BB(int i){
	int ini, fim, mid, ir, is, ip;
	ir = tryCombination( R);
	if(ir > i || ir == -1)
		is = 0;
	else
		is = 1;
	ini = 0; fim = n -1;
	while(ini != fim){
		mid = (ini + fim)/2;
		flip(ini, mid);
		ir = tryCombination(R);
		if(ir > i || ir == -1)
			ip = 0;
		else
			ip = 1;
		flip(ini, mid);

		if(is != ip)
			fim = mid;
		else
			ini = mid + 1;
	} 
	ans[ini] = i;
	R[ini] = is;
	marc[ini] = 1;
}


void exploreCave(int N) {
    n = N;
    for(int i = 0; i < n; i++)
    	BB(i);
    answer( R, ans);

}

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