Submission #1246870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246870		Zicrus	Sphinx's Riddle (IOI24_sphinx)	C++20	100 / 100	85 ms	4132 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 attempted = 0, actual = 0, dummy = 0;
map<vector<int>, int> mem;
int perform_experiment_cached(vector<int> col, ll &counter) {
	attempted++;
    if (mem.count(col)) return mem[col];
	actual++;
	counter++;
    return mem[col] = perform_experiment(col);
}

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

ll ask(ll n, vector<vector<ll>> &adj, vector<ll> &nodes, ll l, ll r, ll col, vector<ll> ids, ll &counter) {
	vector<int> query(n, col);
	ll cnt = 0;
	for (ll i = l; i <= r; i++) if (find(all(ids), i) == ids.end()) { query[nodes[i]] = -1; cnt++; }
	if (col == n && cnt <= 1) return count_components(n, adj, query);
	return perform_experiment_cached(query, counter);
}

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, dummy);
		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, dummy);
				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);
	ll first_cnt = 0, search_cnt = 0, skipped = 0;
	vector<ll> glob_ids;
	for (ll col = 0; col < n; col++) {
		vector<ll> ids;
        auto recent = [&](ll l, ll r) -> optional<ll> {
            optional<ll> res = nullopt;
            for (auto &e : ids) if (e >= l && e <= r) res = e;
            return res;
        };
        auto without = [&](ll e) -> vector<ll> {
            vector<ll> res = ids;
            res.erase(find(all(res), e));
            return res;
        };
        auto count_rem = [&](ll l, ll r) -> ll {
            ll res = r - l + 1;
            for (auto &e : glob_ids) res -= (e >= l && e <= r);
            return res;
        };

		ll _start = ask(n, adj, nodes, 0, nodes.size()-1, n, first_cnt);
		ll start = ask(n, adj, nodes, 0, nodes.size()-1, col, dummy); // 250
		while (start != _start) {
			ll l = 0, r = nodes.size()-1;
			while (l < r) {
				ll mid = l + (r - l) / 2;
				if (count_rem(mid+1, r) == 0) { r = mid; skipped++; continue; }
				if (count_rem(l, mid) == 0) { l = mid + 1; skipped++; continue; }
				auto opt = recent(l, mid);
				if (!opt) {
					ll _q = ask(n, adj, nodes, l, mid, n, first_cnt);
					ll q = ask(n, adj, nodes, l, mid, col, search_cnt);
					if (q != _q) r = mid;
					else l = mid + 1;
				}
				else {
					ll prev = ask(n, adj, nodes, l, mid, n, without(opt.value()), first_cnt);
					ll nw = ask(n, adj, nodes, l, mid, n, ids, search_cnt);
					if (nw >= prev) r = mid;
					else { // opt.value() is isolated
						ll _nw = ask(n, adj, nodes, l, mid, col, search_cnt);
						if (nw != _nw) r = mid;
						else l = mid + 1;
					}
				}
			}
			res[nodes[l]] = col;
			ids.push_back(l);
			glob_ids.push_back(l);
			_start = ask(n, adj, nodes, 0, nodes.size()-1, n, ids, dummy); // 250
		}
	}
	cerr << first_cnt << ' ';
}

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);
	solve_blue(n, adj, res, red);
	cerr << attempted << ' ' << actual << '\n';
	return res;
}

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

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