oj.uz

Submission #991551

# Submission time Handle Problem Language Result Execution time Memory
991551 2024-06-02T12:12:52 Z SanguineChameleon Magic Show (APIO24_show) C++17
100 / 100
 407 ms 389332 KB 
#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;
}
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 389332 KB Correct.
2 Correct 349 ms 389084 KB Correct.
3 Correct 352 ms 389064 KB Correct.
4 Correct 368 ms 389080 KB Correct.
5 Correct 344 ms 389116 KB Correct.
6 Correct 352 ms 389124 KB Correct.
7 Correct 356 ms 389184 KB Correct.
8 Correct 357 ms 389076 KB Correct.
9 Correct 346 ms 389120 KB Correct.
10 Correct 369 ms 389200 KB Correct.
11 Correct 351 ms 389332 KB Correct.
12 Correct 349 ms 389096 KB Correct.

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 389332 KB Correct.
2 Correct 349 ms 389084 KB Correct.
3 Correct 352 ms 389064 KB Correct.
4 Correct 368 ms 389080 KB Correct.
5 Correct 344 ms 389116 KB Correct.
6 Correct 352 ms 389124 KB Correct.
7 Correct 356 ms 389184 KB Correct.
8 Correct 357 ms 389076 KB Correct.
9 Correct 346 ms 389120 KB Correct.
10 Correct 369 ms 389200 KB Correct.
11 Correct 351 ms 389332 KB Correct.
12 Correct 349 ms 389096 KB Correct.
13 Correct 360 ms 389224 KB Correct.
14 Correct 363 ms 389332 KB Correct.
15 Correct 378 ms 389096 KB Correct.
16 Correct 354 ms 389308 KB Correct.
17 Correct 385 ms 389120 KB Correct.
18 Correct 359 ms 389076 KB Correct.
19 Correct 350 ms 389076 KB Correct.
20 Correct 347 ms 389192 KB Correct.
21 Correct 395 ms 389140 KB Correct.
22 Correct 366 ms 389076 KB Correct.
23 Correct 349 ms 389092 KB Correct.
24 Correct 350 ms 389076 KB Correct.

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 389332 KB Correct.
2 Correct 349 ms 389084 KB Correct.
3 Correct 352 ms 389064 KB Correct.
4 Correct 368 ms 389080 KB Correct.
5 Correct 344 ms 389116 KB Correct.
6 Correct 352 ms 389124 KB Correct.
7 Correct 356 ms 389184 KB Correct.
8 Correct 357 ms 389076 KB Correct.
9 Correct 346 ms 389120 KB Correct.
10 Correct 369 ms 389200 KB Correct.
11 Correct 351 ms 389332 KB Correct.
12 Correct 349 ms 389096 KB Correct.
13 Correct 360 ms 389224 KB Correct.
14 Correct 363 ms 389332 KB Correct.
15 Correct 378 ms 389096 KB Correct.
16 Correct 354 ms 389308 KB Correct.
17 Correct 385 ms 389120 KB Correct.
18 Correct 359 ms 389076 KB Correct.
19 Correct 350 ms 389076 KB Correct.
20 Correct 347 ms 389192 KB Correct.
21 Correct 395 ms 389140 KB Correct.
22 Correct 366 ms 389076 KB Correct.
23 Correct 349 ms 389092 KB Correct.
24 Correct 350 ms 389076 KB Correct.
25 Correct 360 ms 389132 KB Correct.
26 Correct 345 ms 389036 KB Correct.
27 Correct 345 ms 389124 KB Correct.
28 Correct 350 ms 389092 KB Correct.
29 Correct 352 ms 389088 KB Correct.
30 Correct 407 ms 389016 KB Correct.
31 Correct 365 ms 389108 KB Correct.
32 Correct 380 ms 388940 KB Correct.
33 Correct 393 ms 389072 KB Correct.
34 Correct 371 ms 388984 KB Correct.
35 Correct 392 ms 389100 KB Correct.
36 Correct 390 ms 389052 KB Correct.
37 Correct 388 ms 389068 KB Correct.
38 Correct 350 ms 389076 KB Correct.
39 Correct 344 ms 389084 KB Correct.
40 Correct 399 ms 389088 KB Correct.
41 Correct 377 ms 389060 KB Correct.
42 Correct 351 ms 389072 KB Correct.
43 Correct 355 ms 389140 KB Correct.
44 Correct 355 ms 389072 KB Correct.