Submission #960280

#	Time	Username	Problem	Language	Result	Execution time	Memory
960280		SoSmolSten	Cave (IOI13_cave)	C++17	100 / 100	558 ms	600 KiB

cave

#include "cave.h"
const int SZ = 5010;
int s[SZ];
int d[SZ];

void flip(int i){
	while(i >= 0){
		if(d[i] == -1){
			s[i] = !s[i];
		}
		--i;
	}
}

void exploreCave(int N) {
	for(int i = 0; i < N; ++i){
		s[i] = 0; d[i] = -1;
	}
	for (int i = 0; i < N; ++i) {
		int v = tryCombination(s);
		if (v == i) flip(N);
		int low = 0, high = N - 1, p = -1;
		while (low <= high) {
			int mid = (low + high) >> 1;
			flip(mid); 
			v = tryCombination(s); 
			flip(mid);
			if (v == i) high = (p = mid) - 1;
			else low = mid + 1;
		}
		d[p] = i;
	}

	answer(s, d);
}

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