Submission #1174857

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174857		trvhung	Cave (IOI13_cave)	C++20	12 / 100	154 ms	508 KiB

cave

#include "cave.h"

void exploreCave(int N) {
	int sw[N], fx[N], ofSw[N];
	for (int i = 0; i < N; ++i)
		fx[i] = -1;

	for (int d = 0; d < N; ++d) {
		for (int i = 0; i < N; ++i)
			sw[i] = fx[i] == -1 ? 0 : fx[i];

		int cur = tryCombination(sw);
		int l = 0, r = N - 1;
		while (l != r) {
			int mid = (l + r) >> 1;
			for (int i = l; i <= mid; ++i)
				sw[i] = fx[i] == -1 ? 1 : fx[i];

			int ask = tryCombination(sw);
			for (int i = l; i <= mid; ++i)
				sw[i] = fx[i] == -1 ? 0 : fx[i];
		
			if (ask == cur) 
				l = mid + 1;
			else
				r = mid;
		}

		fx[l] = (cur == d);
		ofSw[l] = d;
	}

	answer(fx, ofSw);
}

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