제출 #1236784

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1236784		Zicrus	Sphinx's Riddle (IOI24_sphinx)	C++20	36 / 100	42 ms	472 KiB

sphinx

#include <bits/stdc++.h>
#include "sphinx.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(v) v.begin(), v.end()
ll _ = 0;

int count_components(ll N, vector<vector<ll>> &adj, const std::vector<int>& colors) {
	int components_cnt = 0;
	std::vector<bool> vis(N, false);
	for (int i = 0; i < N; i++) {
		if (vis[i])
			continue;
		components_cnt++;

		std::queue<int> q;
		vis[i] = true;
		q.push(i);
		while (!q.empty()) {
			int cur = q.front();
			q.pop();
			for (int nxt : adj[cur])
				if (!vis[nxt] && colors[nxt] == colors[cur]) {
					vis[nxt] = true;
					q.push(nxt);
				}
		}
	}
	return components_cnt;
}

ll expected(ll n, vector<vector<ll>> &adj, vector<ll> &nodes, ll l, ll r, set<ll> &exc) {
	vector<int> query(n, n);
	for (ll i = l; i <= r; i++) if (!exc.count(nodes[i])) query[nodes[i]] = 0;
	return count_components(n, adj, query);
}

ll ask(ll n, vector<vector<ll>> &adj, vector<ll> &nodes, ll l, ll r, ll col) {
	vector<int> query(n, col);
	for (ll i = l; i <= r; i++) query[nodes[i]] = -1;
	return perform_experiment(query);
}

map<pll, ll> mem;
ll ask_sphinx(ll n, vector<vector<ll>> &adj, vector<ll> &nodes, ll l, ll r) {
	if (l == r) {
		vector<int> colors(n, n);
		colors[nodes[l]] = 0;
		return count_components(n, adj, colors);
	}
	if (mem.count({l, r})) return mem[{l, r}];
	return mem[{l, r}] = ask(n, adj, nodes, l, r, n);
}

void solve_red(ll n, vector<vector<ll>> &adj, vector<int> &res, vector<ll> &red) {
	vector<ll> nodes;
	for (ll i = 0; i < n; i++) if (red[i]) nodes.push_back(i);
	for (ll col = 0; col < n; col++) {
		set<ll> exc;
		ll _start = expected(n, adj, nodes, 0, nodes.size()-1, exc);
		ll start = ask(n, adj, nodes, 0, nodes.size()-1, col);
		while (start != _start) {
			ll l = 0, r = nodes.size()-1;
			while (l < r) {
				ll mid = l + (r - l) / 2;
				ll _q = expected(n, adj, nodes, l, mid, exc);
				ll q = ask(n, adj, nodes, l, mid, col);
				if (q != _q) r = mid;
				else l = mid + 1;
			}
			res[nodes[l]] = col;
			exc.insert(nodes[l]);
			_start = expected(n, adj, nodes, 0, nodes.size()-1, exc);
		}
	}
}

void solve_blue(ll n, vector<vector<ll>> &adj, vector<int> &res, vector<ll> &red) {
	vector<ll> nodes;
	for (ll i = 0; i < n; i++) if (red[i]) nodes.push_back(i);
	for (ll col = 0; col < n; col++) {
		vector<ll> exc;
		//ll _start = ask_sphinx(n, adj, nodes, 0, nodes.size()-1, exc);
		ll start = ask(n, adj, nodes, 0, nodes.size()-1, col);
		//while (start != _start) {
			ll l = 0, r = nodes.size()-1;
			while (l < r) {
				ll mid = l + (r - l) / 2;
				//ll _q = ask_sphinx(n, adj, nodes, l, mid, exc);
				ll q = ask(n, adj, nodes, l, mid, col);
				//if (q != _q) r = mid;
				//else l = mid + 1;
			}
			res[l] = col;
			exc.push_back(l);
			//_start = ask_sphinx(n, adj, nodes, 0, nodes.size()-1, exc);
		//}
	}
}

vector<int> find_colours(int n, vector<int> u, vector<int> v) {
	int m = u.size();
	vector<vector<ll>> adj(n);
	for (ll i = 0; i < m; i++) {
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	vector<ll> red(n);
	for (ll i = 0; i < n; i++) {
		red[i] = true;
		for (auto &e : adj[i]) if (red[e]) red[i] = false;
	}
	vector<int> res(n, -1);
	solve_red(n, adj, res, red);
	for (auto &e : red) e = !e;
	solve_red(n, adj, res, red);
	//solve_blue(n, adj, res, red);
	return res;
}

#ifdef TEST
#include "grader.cpp"
#endif

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