Submission #1124318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124318		Rainmaker2627	Cave (IOI13_cave)	C++20	0 / 100	210 ms	504 KiB

cave

#include "cave.h"

void setPrefix(int N, int l, int r, int (&s)[], int (&cor)[]) {
	for (int i = 0; i < l; ++i) s[i]=(cor[i]==-1?1-r:cor[i]);
	for (int i = l; i < N; ++i) s[i]=(cor[i]==-1?r:cor[i]);
}

void exploreCave(int N) {
	int s[N]={0}, cor[N]={0}, ans[N]={0};
	for (int i = 0; i < N; ++i) s[i]=0, cor[i]=ans[i]=-1;

	for (int i = 1; i <= N; ++i) {
		setPrefix(N, 0, 0, s, cor);
		int l=0, r=N;
		cor[i-1]=(tryCombination(s)==i);
		while (l<r) {
			int mid=(l+r)/2;
			setPrefix(N, mid, cor[i-1], s, cor);
			int t=tryCombination(s);
			if (t==i) l=mid+1;
			else r=mid;
		} ans[r]=i;
	} answer(cor, ans);
}

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