Submission #731087

#	Time	Username	Problem	Language	Result	Execution time	Memory
731087		pedroslrey	Cave (IOI13_cave)	C++17	100 / 100	636 ms	664 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"

using namespace std;

const int MAXN = 5e3 + 10;

int ss[MAXN], perm[MAXN], comb[MAXN], ans[MAXN];

int test() {
	int x = tryCombination(ss);
	if (x != -1) return x;
	return 1e9;
}

void exploreCave(int n) {
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j)
			ss[j] = 0;
		for (int j = 0; j < i; ++j)
			ss[perm[j]] = comb[perm[j]];

		bool val;
		if (test() > i) val = false;
		else val = true;

		//cerr << "DOOR " << i << " " << val << "\n";

		int l = 0, r = n - 1;
		while (l < r) {
			int m = (l + r)/2;	
			for (int j = 0; j < n; ++j)
				ss[j] = 0;
			for (int j = l; j <= m; ++j)
				ss[j] = 1;
			for (int j = 0; j < i; ++j)
				ss[perm[j]] = comb[perm[j]];

			if (test() > i)
				if (val) r = m;
				else l = m + 1;
			else if (val) l = m + 1;
				else r = m;
		}

		//cerr << "POSITION " << l << "\n";

		perm[i] = l;
		comb[perm[i]] = val;
		ans[l] = i;
	}

	answer(comb, ans);
}

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