제출 #991551

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
991551		SanguineChameleon	마술쇼 (APIO24_show)	C++17	100 / 100	407 ms	389332 KiB

Alice

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

namespace alice_rng {
	unsigned long long state = 88172645463325252LL;

	long long rand_bits(int k) {
		state ^= (state << 13);
		state ^= (state >> 7);
		state ^= (state << 17);
		return (state & ((1LL << k) - 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 = rand_bits(k);
			if (x <= d) {
				return l + x;
			}
		}
	}

	template <typename T>
	void shuffle(T *first, T *last) {
		int n = last - first;
		for (int i = 0; i < n; i++) {
			T *p1 = first + i;
			T *p2 = first + rand_int(i, n - 1);
			int tmp = *p1;
			*p1 = *p2;
			*p2 = tmp;
		}
	}
}

namespace alice_edges {
	const int K = 60;
	const int M = 83;
	const int N = K * M + 2;
	long long weight[N][N];
	int pos[K * M];

	void build() {
		for (int i = 0; i < K; i++) {
			fill(pos + i * M, pos + (i + 1) * M, i);
		}
		alice_rng::shuffle(pos, pos + K * M);
		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_bits(1);
					sum += weight[i][j];
				}
				if (sum != 0 && sum != i) {
					break;
				}
			}
			alice_rng::shuffle(weight[i], weight[i] + 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;

	long long rand_bits(int k) {
		state ^= (state << 13);
		state ^= (state >> 7);
		state ^= (state << 17);
		return (state & ((1LL << k) - 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 = rand_bits(k);
			if (x <= d) {
				return l + x;
			}
		}
	}

	template <typename T>
	void shuffle(T *first, T *last) {
		int n = last - first;
		for (int i = 0; i < n; i++) {
			T *p1 = first + i;
			T *p2 = first + rand_int(i, n - 1);
			int tmp = *p1;
			*p1 = *p2;
			*p2 = tmp;
		}
	}
}

namespace bob_edges {
	const int K = 60;
	const int M = 83;
	const int N = K * M + 2;
	long long weight[N][N];
	int pos[K * M];

	void build() {
		for (int i = 0; i < K; i++) {
			fill(pos + i * M, pos + (i + 1) * M, i);
		}
		bob_rng::shuffle(pos, pos + K * M);
		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_bits(1);
					sum += weight[i][j];
				}
				if (sum != 0 && sum != i) {
					break;
				}
			}
			bob_rng::shuffle(weight[i], weight[i] + 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: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65