Submission #1188316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188316		hcng	Sphinx's Riddle (IOI24_sphinx)	C++20	12 / 100	38 ms	916 KiB

sphinx

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

#define Query(x) perform_experiment(x)

vector<int> find_colours(int n, vector<int> X, vector<int> Y) {
	vector<int> G(n);
	for (int i = 0; i < n; i++) G[i] = i;
	auto find = [&](const auto &self, int x) -> int {return G[x] == x? x : G[x] = self(self, G[x]);};
	auto check = [&](int M, int i) -> bool {
		set<int> s;
		vector<int> E(n, n);
		for (int j = M; j <= i; j++) {
			s.insert(G[j]);
			E[j] = -1;
		}
		int x = Query(E) + (M == 0 && i == n - 1);
		cerr << s.size() << ' ' << x << endl;
		return x < 1 + s.size();
	};
	for (int i = 1; i < n; i++) {
		int L = 0, R = i;
		while (L < R) {
			int M = L + R + 1 >> 1;
			if (check(M, i)) {
				L = M;
			} else {
				R = M - 1;
			}
		}
		if (check(0, i)) G[i] = find(find, L);
	}
	for (int i = 0; i < n; i++) find(find, i);
	return G;
}

• Subtask 0: 0 / 0
• Subtask 1: 1.5 / 3
• Subtask 2: 0 / 7
• Subtask 3: 0 / 33
• Subtask 4: 10.5 / 21
• Subtask 5: 0 / 36