Submission #1210540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210540		Mousa_Aboubaker	Sphinx's Riddle (IOI24_sphinx)	C++20	1.50 / 100	2 ms	424 KiB

sphinx

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

vector<int> find_colours(int N, vector<int> X, vector<int> Y)
{
	int n = N, m = (int)X.size();
	vector<int> x = X, y = Y;
	vector<int> par(n), sz(n, 1);
	iota(par.begin(), par.end(), 0);
	auto findd = [&](auto self, int u) -> int
	{
		return par[u] = (par[u] == u ? u : self(self, par[u]));
	};
	auto unite = [&](int u, int v) -> bool
	{
		u = findd(findd, u);
		v = findd(findd, v);
		if (u == v)
			return false;
		if (sz[u] > sz[v])
			swap(u, v);
		sz[v] += sz[u];
		par[u] = v;
		return true;
	};
	vector adj(n, vector<int>());
	for (int i = 0; i < m; i++)
	{
		adj[x[i]].push_back(y[i]);
		adj[y[i]].push_back(x[i]);
	}
	for(int i = 0; i < n; i++)
		sort(adj[i].begin(), adj[i].end());
	for (int i = 0; i < n - 1; i++)
	{
		int l = i + 1, r = n - 1, ans = -1;
		while (r - l > 1)
		{
			int md = l + (r - l) / 2;
			vector<int> e(n, N);
			for (int j = l; j <= md; j++)
				e[j] = -1;
			int cnt = perform_experiment(e);
			e[i] = -1;
			int cnt2 = perform_experiment(e);
			if (cnt2 == cnt)
			{
				r = md;
			}
			else
			{
				l = md + 1;
			}
		}
		vector<int> e(n, N);
		e[i] = -1;
		e[l] = -1;
		int cnt = perform_experiment(e);
		if(n == 2)
		{
			if(cnt == 1)
				unite(i, l);
		}
		else
		{
			if(cnt == 2)
				unite(i, l);
		}
		
		e[i] = -1;
		e[l] = N;
		e[r] = -1;
		cnt = perform_experiment(e);
		if(n == 2)
		{
			if(cnt == 1)
				unite(i, l);
		}
		else
		{
			if(cnt == 2)
				unite(i, l);
		}
		// for (int j : adj[i])
		// 	adj[j].erase(find(adj[j].begin(), adj[j].end(), i));
	}
	set<int> st;
	for (int i = 0; i < n; i++)
		st.insert(findd(findd, i));
	int j = 0;
	map<int, int> mp;
	for (auto i : st)
	{
		mp[i] = j++;
	}
	vector<int> res(n);
	for (int i = 0; i < n; i++)
		res[i] = mp[findd(findd, i)];
	return res;
}

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