Submission #1076472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076472		EntityPlantt	Cave (IOI13_cave)	C++17	12 / 100	371 ms	700 KiB

cave

#include "cave.h"
#include <vector>

bool query(int I, int N, int S[], std::vector <int> &U, int L, int R, bool rev) {
	int Q[N];
	for (int i = 0; i < N; i++) Q[i] = S[i];
	for (int &i : U) Q[U[i]] = !rev;
	for (int i = L; i <= R; i++) Q[U[i]] = rev;
	int res = tryCombination(Q);
	return res > I || res < 0;
}

void exploreCave(int N) {
	int S[N] = {}, D[N];
	std::vector <int> undiscovered;
	for (int i = 0; i < N; i++) undiscovered.push_back(i);
	for (int i = 0; i < N; i++) {
		int l = 0, r = undiscovered.size() - 1;
		bool reverse = query(i, N, S, undiscovered, l, r, 1);
		while (l < r) {
			int m = l + r >> 1;
			if (query(i, N, S, undiscovered, l, m, reverse)) r = m;
			else l = m + 1;
		}
		D[undiscovered[l]] = i;
		S[undiscovered[l]] = reverse;
		undiscovered.erase(undiscovered.begin() + l);
	}
	answer(S, D);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:21:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |    int m = l + r >> 1;
      |            ~~^~~

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