Submission #991525

#	Time	Username	Problem	Language	Result	Execution time	Memory
991525		SanguineChameleon	Magic Show (APIO24_show)	C++17	0 / 100	1020 ms	195464 KiB

Alice

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

namespace alice_rng {
	unsigned long long state = 88172645463325252LL;

	int rand_bit() {
		state ^= (state << 13);
		state ^= (state >> 7);
		state ^= (state << 17);
		return (state & 1);
	}

	long long rand_int(long long l, long long r) {
		long long d = r - l;
		int k = 0;
		while ((1LL << k) <= d) {
			k++;
		}
		while (true) {
			long long x = 0;
			for (int i = 0; i < k; i++) {
				x |= ((long long)rand_bit() << i);
			}
			if (x <= d) {
				return l + x;
			}
		}
	}

	template <typename T>
	void shuffle(vector<T> &a) {
		int n = a.size();
		for (int i = 0; i < n; i++) {
			swap(a[i], a[rand_int(i, n - 1)]);
		}
	}
}

namespace alice_edges {
	const int K = 60;
	const int M = 83;
	const int N = K * M + 2;
	vector<vector<long long>> weight;

	void build() {
		weight.resize(N);
		for (int i = 1; i < N; i++) {
			weight[i].resize(i);
		}
		vector<int> pos(K * M);
		for (int i = 0; i < K; i++) {
			fill(pos.begin() + i * M, pos.begin() + (i + 1) * M, i);
		}
		alice_rng::shuffle(pos);
		long double max_p = 0.0L;
		for (int i = 2; i < N; i++) {
			while (true) {
				int sum = 0;
				for (int j = 0; j < i; j++) {
					weight[i][j] = alice_rng::rand_bit();
					sum += weight[i][j];
				}
				if (sum != 0 && sum != i) {
					max_p = max(max_p, 1.0L * max(sum, i - sum) / i);
					break;
				}
			}
			alice_rng::shuffle(weight[i]);
			for (int j = 0; j < i; j++) {
				weight[i][j] <<= pos[i - 2];
			}
		}
	}
}

vector<pair<int, int>> Alice() {
	alice_edges::build();
	long long X = setN(alice_edges::N);
	vector<pair<int, int>> res;
	for (int i = 1; i < alice_edges::N; i++) {
		while (true) {
			int j = alice_rng::rand_int(0, i - 1);
			if ((X & alice_edges::weight[i][j]) == alice_edges::weight[i][j]) {
				res.emplace_back(j + 1, i + 1);
				break;
			}
		}
	}
	return res;
}

Bob

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

namespace bob_rng {
	unsigned long long state = 88172645463325252LL;

	int rand_bit() {
		state ^= (state << 13);
		state ^= (state >> 7);
		state ^= (state << 17);
		return (state & 1);
	}

	long long rand_int(long long l, long long r) {
		long long d = r - l;
		int k = 0;
		while ((1LL << k) <= d) {
			k++;
		}
		while (true) {
			long long x = 0;
			for (int i = 0; i < k; i++) {
				x |= ((long long)rand_bit() << i);
			}
			if (x <= d) {
				return l + x;
			}
		}
	}

	template <typename T>
	void shuffle(vector<T> &a) {
		int n = a.size();
		for (int i = 0; i < n; i++) {
			swap(a[i], a[rand_int(i, n - 1)]);
		}
	}
}

namespace bob_edges {
	const int K = 60;
	const int M = 83;
	const int N = K * M + 2;
	vector<vector<long long>> weight;

	void build() {
		weight.resize(N);
		for (int i = 1; i < N; i++) {
			weight[i].resize(i);
		}
		vector<int> pos(K * M);
		for (int i = 0; i < K; i++) {
			fill(pos.begin() + i * M, pos.begin() + (i + 1) * M, i);
		}
		bob_rng::shuffle(pos);
		long double max_p = 0.0L;
		for (int i = 2; i < N; i++) {
			while (true) {
				int sum = 0;
				for (int j = 0; j < i; j++) {
					weight[i][j] = bob_rng::rand_bit();
					sum += weight[i][j];
				}
				if (sum != 0 && sum != i) {
					max_p = max(max_p, 1.0L * max(sum, i - sum) / i);
					break;
				}
			}
			bob_rng::shuffle(weight[i]);
			for (int j = 0; j < i; j++) {
				weight[i][j] <<= pos[i - 2];
			}
		}
	}
}

long long Bob(vector<pair<int, int>> V) {
	bob_edges::build();
	long long res = 0;
	for (auto [j, i]: V) {
		j--;
		i--;
		res |= bob_edges::weight[i][j];
	}
	return res;
}

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