Submission #112529

#	Time	Username	Problem	Language	Result	Execution time	Memory
112529		tjd229	Cave (IOI13_cave)	C++14	100 / 100	755 ms	540 KiB

cave

#include "cave.h"
#define reg register
int rem;//int _N;
void fill(int *a, int val, int s, int e, int *chair) {
	for (reg int i = 0; i < s; ++i) a[chair[i]] = 1 - val;
	for (reg int i = s; i <= e; ++i) a[chair[i]] = val;
	for (reg int i = e + 1; i < rem; ++i) a[chair[i]] = 1 - val;
}
void exploreCave(int N) {
	//_N = N;
	int chair[5000], S[5000], D[5000];
	
	rem = N;
	for (reg int i = 0; i < N; ++i) chair[i] = i;
	for (int i = 0; i < N; ++i) {
		int val = 0;
		fill(S, val, 0, rem - 1, chair);
		if (tryCombination(S) == i) val = 1;
		int l = 0, r = rem - 1;
		int pos = -1;
		while (l <= r) {
			int m = (l + r) >> 1;
			fill(S, val, l, m, chair);
			if (tryCombination(S) == i) l = m + 1;
			else r = m - 1, pos = m;
		}
		S[chair[pos]] = val;
		D[chair[pos]] = i;
		--rem;
		chair[pos] ^= chair[rem] ^= chair[pos] ^= chair[rem];
	}
	answer(S, D);
}

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