Submission #1780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1780		kriii	Cave (IOI13_cave)	C++98	100 / 100	435 ms	628 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;

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

	for (i=0;i<N;i++){
		l = 0; r = N-1;
		prev = norm(tryCombination(S),N);
		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){
				if (next > i) l = m + 1;
				else r = m;
			}
			else{
				if (next > i) r = m;
				else l = m + 1;
			}
		}
		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