Submission #991256

#	Time	Username	Problem	Language	Result	Execution time	Memory
991256		vjudge3	Magic Show (APIO24_show)	C++17	100 / 100	4 ms	1340 KiB

Alice

#include <bits/stdc++.h>
#include "Alice.h"
using namespace std;
using ll = long long;

namespace alice {
	mt19937_64 r (chrono::high_resolution_clock().now().time_since_epoch().count()), fixedr (1054);
	const int base = 2;
	const ll inf = 1e18;
	int mp[5005], mpr[5005];
	ll rnd (ll mn, ll mx, mt19937_64& gen) {
		return uniform_int_distribution<ll> (mn, mx) (gen);
	}
}
using namespace alice;

vector<pair<int, int>> Alice () {
	ll x = setN(5000);
	vector<int> perm (5000);
	for (int i = 0; i < 5000; i++) perm[i] = i;
	shuffle(perm.begin(), perm.end(), fixedr);
	for (int i = 0; i < 5000; i++) mp[i+1] = perm[i]+1;
	x--;
	vector<ll> units;
	ll lg = 0;
	for (ll power = 1; power < inf; power *= base) {
		units.push_back(x % base);
		x /= base;
		lg++;
	}
	ll m = (base+1) * lg;
	vector<int> chain;
	for (int i = 0; i < lg; i++) {
		chain.push_back(i * (base+1) + 1);
		chain.push_back(i * (base+1) + 2 + units[i]);
		if (rnd(0, 1, r)) swap(chain.back(), chain.end()[-2]);
	}
	for (int i = m; i+m <= 5000; i += m) {
		for (int j = 0; j < lg*2; j += 2) {
			chain.push_back(i+chain[j]);
			chain.push_back(i+chain[j+1]);
			if (rnd(0, 1, r)) swap(chain.back(), chain.end()[-2]);
		}
	}
	vector<bool> used (5001);
	for (auto& u : chain) used[u] = true;
	for (int i = 1; i <= 5000; i++) if (!used[i]) {
		int ins = rnd(0, chain.size(), r);
		while ((ins && (i-1) / (base+1) == (chain[ins-1]-1) / (base+1) && !((chain[ins-1]-1) % (base+1))) ||
			(ins < (int) chain.size() && (i-1) / (base+1) == (chain[ins]-1) / (base+1) && !((chain[ins]-1) % (base+1))) ||
			(ins && ins < (int) chain.size() && (chain[ins-1]-1) / (base+1) == (chain[ins]-1) / (base+1) && (!((chain[ins-1]-1) % (base+1)) || !((chain[ins]-1) / (base+1))))
			)
				ins = rnd(0, chain.size(), r);
		chain.insert(chain.begin() + ins, i);
	}
	vector<pair<int, int>> res;
	for (int i = 0; i+1 < (int) chain.size(); i++) res.push_back({chain[i], chain[i+1]});
	for (auto& [u, v] : res) {
		u = mp[u], v = mp[v];
		if (u > v) swap(u, v);
	}
	sort(res.begin(), res.end());
	return res;
}

Bob

#include <bits/stdc++.h>
#include "Bob.h"
using namespace std;
using ll = long long;

namespace bob {
	mt19937_64 r (chrono::high_resolution_clock().now().time_since_epoch().count()), fixedr (1054);
	const int base = 2;
	const ll inf = 1e18;
	int mp[5005], mpr[5005];
	ll rnd (ll mn, ll mx, mt19937_64& gen) {
		return uniform_int_distribution<ll> (mn, mx) (gen);
	}
}
using namespace bob;

ll Bob (vector<pair<int, int>> edges) {
	vector<int> perm (5000);
	for (int i = 0; i < 5000; i++) perm[i] = i;
	shuffle(perm.begin(), perm.end(), fixedr);
	for (int i = 0; i < 5000; i++) mpr[perm[i]+1] = i+1;
	for (auto& [u, v] : edges) u = mpr[u], v = mpr[v];
	ll lg = 0;
	for (ll power = 1; power < inf; power *= base) lg++;
	vector<ll> units (lg);
	for (int i = 0; i < lg; i++) units[i] = rnd(0, 1, r);
	ll m = (base+1) * lg, mx = 5000/m*m;
	for (auto& [u, v] : edges) if (u <= mx && v <= mx && (u-1) / (base+1) == (v-1) / (base+1) && (!((u-1) % (base+1)) || !((v-1) % (base+1))))
		units[(u-1) % m / (base+1)] = (u-1) % (base+1) + (v-1) % (base+1) - 1;
	ll res = 0;
	for (ll power = 1, i = 0; power < inf; power *= base, i++) res += power * units[i];
	return res+1;
}

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