Submission #965598

#	Time	Username	Problem	Language	Result	Execution time	Memory
965598		IBory	Cave (IOI13_cave)	C++17	100 / 100	313 ms	864 KiB

cave

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

const int MAX = 5005;
int C[MAX], S[MAX], D[MAX], ID[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[D[p]] = S[D[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];
			ID[cand[0]] = n;
			S[D[n]] = !init;
			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] = cand[r];
		ID[cand[r]] = n;
		S[D[n]] = !init;
	}

	answer(S, ID);
}

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