Submission #1212781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212781		k1r1t0	Magic Show (APIO24_show)	C++20	100 / 100	2 ms	632 KiB

Alice

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll setN(int n);

vector<pair<int, int>> Alice() {
///////////////////////////////////////////////////////////////
	const int K = 60;
	const int T = 83;
	const int N = K * T;
	const int S = 2341234;
	mt19937 rng(S);
	vector<int> ord(N);
	iota(begin(ord), end(ord), 0);
	shuffle(begin(ord), end(ord), rng);
	vector<int> bt[K];
	for (int i = 0; i < K; i++) {
		bt[i].clear();
		for (int j = i * T; j < (i + 1) * T; j++)
			bt[i].push_back(ord[j]);
	}
	vector<int> zero(N), one(N);
	for (int i = 0; i < N; i++) {
		int cnt = i + 2;
		zero[i] = rng() % cnt;
		one[i] = rng() % (cnt - 1);
		if (zero[i] <= one[i]) one[i]++;
		zero[i] -= 2;
		one[i] -= 2;
	}
///////////////////////////////////////////////////////////////
	ll X = setN(N + 2);
	vector<pair<int, int>> tt;
	for (int i = 0; i < K; i++) {
		int b = (X >> i) & 1;
		for (int j : bt[i]) {
			int k = (b == 0 ? zero[j] : one[j]);
			tt.push_back({j + 3, k + 3});
		}
	}
	tt.push_back({1, 2});
	return tt;
///////////////////////////////////////////////////////////////
}

Bob

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll Bob(vector<pair<int, int>> V) {
///////////////////////////////////////////////////////////////
	const int K = 60;
	const int T = 83;
	const int N = K * T;
	const int S = 2341234;
	mt19937 rng(S);
	vector<int> ord(N);
	iota(begin(ord), end(ord), 0);
	shuffle(begin(ord), end(ord), rng);
	vector<int> bt[K];
	for (int i = 0; i < K; i++) {
		bt[i].clear();
		for (int j = i * T; j < (i + 1) * T; j++)
			bt[i].push_back(ord[j]);
	}
	vector<int> zero(N), one(N);
	for (int i = 0; i < N; i++) {
		int cnt = i + 2;
		zero[i] = rng() % cnt;
		one[i] = rng() % (cnt - 1);
		if (zero[i] <= one[i]) one[i]++;
		zero[i] -= 2;
		one[i] -= 2;
	}
///////////////////////////////////////////////////////////////
	int vv[N];
	for (int i = 0; i < N; i++)
		vv[i] = -3;
	for (auto [u, v] : V) {
		if (u > v) swap(u, v);
		if (v >= 2)
			vv[v - 3] = u - 3;
	}
	ll X = 0;
	for (int i = 0; i < K; i++) {
		int b = -1;
		for (int j : bt[i]) {
			if (vv[j] == -3) continue;
			if (vv[j] == zero[j]) b = 0;
			else b = 1;
			break;
		}
		assert(b != -1);
		if (b) X |= (1ll << i);
	}
	return X;
///////////////////////////////////////////////////////////////
}

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65