Submission #1781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1781		kriii	Cave (IOI13_cave)	C++98	100 / 100	342 ms	564 KiB

cave

#include "cave.h"

int S[5050],D[5050],C[5050];

int norm(int x, int n){if (x < 0) x += n + 1; return x;}

void exploreCave(int N) {
	int i,j,l,r,m,prev,next,mod=1;

	for (i=0;i<N;i++) S[i] = 0, C[i] = 1;

	for (i=0;i<N;i++){
		if (mod) prev = norm(tryCombination(S),N);
		l = 0; r = N-1;
		while (l < r){
			m = (l + r) / 2;
			for (j=l;j<=m;j++) S[j] ^= C[j];
			next = norm(tryCombination(S),N);
			for (j=l;j<=m;j++) S[j] ^= C[j];

			if ((prev > i) ^ (next > i)) r = m;
			else l = m + 1;
		}
		mod = prev <= i;
		if (prev <= i) S[l] = !S[l];
		D[l] = i; C[l] = 0;
	}

	answer(S,D);
}

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