oj.uz

Submission #991256

# Submission time Handle Problem Language Result Execution time Memory
991256 2024-06-01T16:28:21 Z vjudge3 Magic Show (APIO24_show) C++17
100 / 100
 4 ms 1340 KB 
#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;
}
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1076 KB Correct.
2 Correct 1 ms 1076 KB Correct.
3 Correct 1 ms 1076 KB Correct.
4 Correct 2 ms 1076 KB Correct.
5 Correct 2 ms 1076 KB Correct.
6 Correct 2 ms 1180 KB Correct.
7 Correct 3 ms 1080 KB Correct.
8 Correct 3 ms 1080 KB Correct.
9 Correct 1 ms 1080 KB Correct.
10 Correct 1 ms 1076 KB Correct.
11 Correct 1 ms 1088 KB Correct.
12 Correct 2 ms 1088 KB Correct.

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1076 KB Correct.
2 Correct 1 ms 1076 KB Correct.
3 Correct 1 ms 1076 KB Correct.
4 Correct 2 ms 1076 KB Correct.
5 Correct 2 ms 1076 KB Correct.
6 Correct 2 ms 1180 KB Correct.
7 Correct 3 ms 1080 KB Correct.
8 Correct 3 ms 1080 KB Correct.
9 Correct 1 ms 1080 KB Correct.
10 Correct 1 ms 1076 KB Correct.
11 Correct 1 ms 1088 KB Correct.
12 Correct 2 ms 1088 KB Correct.
13 Correct 2 ms 1076 KB Correct.
14 Correct 2 ms 1080 KB Correct.
15 Correct 3 ms 1076 KB Correct.
16 Correct 2 ms 1076 KB Correct.
17 Correct 3 ms 1072 KB Correct.
18 Correct 3 ms 1340 KB Correct.
19 Correct 3 ms 1076 KB Correct.
20 Correct 2 ms 1076 KB Correct.
21 Correct 1 ms 1072 KB Correct.
22 Correct 1 ms 1076 KB Correct.
23 Correct 1 ms 1088 KB Correct.
24 Correct 2 ms 1080 KB Correct.

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1076 KB Correct.
2 Correct 1 ms 1076 KB Correct.
3 Correct 1 ms 1076 KB Correct.
4 Correct 2 ms 1076 KB Correct.
5 Correct 2 ms 1076 KB Correct.
6 Correct 2 ms 1180 KB Correct.
7 Correct 3 ms 1080 KB Correct.
8 Correct 3 ms 1080 KB Correct.
9 Correct 1 ms 1080 KB Correct.
10 Correct 1 ms 1076 KB Correct.
11 Correct 1 ms 1088 KB Correct.
12 Correct 2 ms 1088 KB Correct.
13 Correct 2 ms 1076 KB Correct.
14 Correct 2 ms 1080 KB Correct.
15 Correct 3 ms 1076 KB Correct.
16 Correct 2 ms 1076 KB Correct.
17 Correct 3 ms 1072 KB Correct.
18 Correct 3 ms 1340 KB Correct.
19 Correct 3 ms 1076 KB Correct.
20 Correct 2 ms 1076 KB Correct.
21 Correct 1 ms 1072 KB Correct.
22 Correct 1 ms 1076 KB Correct.
23 Correct 1 ms 1088 KB Correct.
24 Correct 2 ms 1080 KB Correct.
25 Correct 3 ms 1076 KB Correct.
26 Correct 2 ms 1084 KB Correct.
27 Correct 2 ms 1080 KB Correct.
28 Correct 2 ms 1088 KB Correct.
29 Correct 3 ms 1088 KB Correct.
30 Correct 4 ms 1076 KB Correct.
31 Correct 2 ms 1076 KB Correct.
32 Correct 1 ms 1092 KB Correct.
33 Correct 2 ms 1076 KB Correct.
34 Correct 2 ms 1076 KB Correct.
35 Correct 2 ms 1080 KB Correct.
36 Correct 1 ms 1076 KB Correct.
37 Correct 2 ms 1084 KB Correct.
38 Correct 2 ms 1072 KB Correct.
39 Correct 3 ms 1076 KB Correct.
40 Correct 1 ms 1076 KB Correct.
41 Correct 1 ms 1096 KB Correct.
42 Correct 1 ms 1092 KB Correct.
43 Correct 1 ms 1076 KB Correct.
44 Correct 3 ms 1076 KB Correct.