Submission #965282

#	Time	Username	Problem	Language	Result	Execution time	Memory
965282		IBory	Cave (IOI13_cave)	C++17	0 / 100	187 ms	584 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;

const int MAX = 5005;
int C[MAX], S[MAX], D[MAX];

void exploreCave(int N) {
	for (int n = 0; n < N; ++n) {
		memset(C, 0x3f, sizeof(C));
		vector<int> cand;
		for (int p = 0; p < n; ++p) C[p] = S[p];
		for (int i = 0; i < N; ++i) {
			if (1e9 < C[i]) {
				cand.push_back(i);
				C[i] = 0;
			}
		}
		
		int init = tryCombination(C) != n;
		if (cand.size() == 1) {
			D[n] = cand[0];
			S[n] = (init == n);
			break;
		}

		int l = -1, r = cand.size() - 1;
		while (l + 1 < r) {
			int mid = (l + r) >> 1;
			for (int i = 0; i < mid; ++i) C[cand[i]] = 1;

			int go = tryCombination(C) != n;
			(init == go ? l : r) = mid;

			for (int i = 0; i < mid; ++i) C[cand[i]] = 0;
		}

		D[n] = r;
		S[n] = !init;
	}

	answer(S, D);
}

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