Submission #207776

#	Time	Username	Problem	Language	Result	Execution time	Memory
207776		mode149256	Cave (IOI13_cave)	C++14	100 / 100	463 ms	640 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
void exploreCave(int N) {
	int *ans = new int[N];
	int *D = new int[N];

	// 00001111
	for (int i = 0; i < N; ++i)
		ans[i] = -1;

	auto print = [&](int *vec) {
		for (int i = 0; i < N; ++i)
			printf("%d ", vec[i]);

		printf("\n");
	};

	auto bandyk = [&](int *vec) {
		int ret = tryCombination(vec);
		return ret == -1 ? N : ret;
	};

	for (int h = 0; h < N; ++h)
	{
		int *A = new int[N];

		for (int j = 0; j < N; ++j)
		{
			if (ans[j] == -1) A[j] = 1;
			else A[j] = ans[j];
		}

		int manoCorrect = int(bandyk(A) > h);
		// printf("ats = %d, bandau: ", manoCorrect); print(A);

		int l = 0, r = N - 1;

		while (l < r) {
			int m = (l + r) / 2;

			for (int i = l; i <= r; ++i)
				if (ans[i] == -1)
					A[i] = int(m < i);

			int ans = (bandyk(A) > h);
			// printf("l = %d, r = %d, ats = %d, bandau: ",
			// l, r, ans); print(A);

			if (ans ^ manoCorrect ) {
				r = m;
			} else
				l = m + 1;
		}

		ans[l] = manoCorrect;
		D[l] = h;

		// printf("h = %d, l = %d, manoCorrect %d\n", h, l, manoCorrect);
		delete[] A;
	}

	answer(ans, D);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:11:7: warning: variable 'print' set but not used [-Wunused-but-set-variable]
  auto print = [&](int *vec) {
       ^~~~~

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