oj.uz

Submission #668221

# Submission time Handle Problem Language Result Execution time Memory
668221 2022-12-03T10:37:50 Z Sohsoh84 Flight to the Ford (BOI22_communication) C++17
74 / 100
 3052 ms 2068 KB 
#include"communication.h"
#include <bits/stdc++.h>
//
// --- Sample implementation for the task communication ---
//
// To compile this program with the sample grader, place:
//     communication.h communication_sample.cpp sample_grader.cpp
// in a single folder, then open the terminal in this directory (right-click onto an empty spot in the directory,
// left click on "Open in terminal") and enter e.g.:
//     g++ -std=c++17 communication_sample.cpp sample_grader.cpp
// in this folder. This will create a file a.out in the current directory which you can execute from the terminal
// as ./a.out
// See task statement or sample_grader.cpp for the input specification

using namespace std;

const int LOG = 30;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int f(int x) {
	return 31 - __builtin_clz(x);
}

void encode(int N, int X) {
	int ans1 = 0, ans2 = 1, lst = -1, lst_ans = -1;
	for (int i = 1; i < LOG; i++) {
		if (ans2 < ans1) swap(ans1, ans2);

		if (ans1 == ans2) {
			ans2 ^= (1 << i);
			continue;
		}

		int x = f(ans1 ^ ans2);
		int a = (lst == x ? lst_ans : send((X >> x) & 1)), b = send((X >> i) & 1), c = send((X >> i) & 1);
		lst = i;
		lst_ans = c;

		if (b == c) {
			ans1 ^= (b << i);
			ans2 ^= (b << i);
			continue;
		}

		int d = send((X >> x) & 1);
		lst = x;
		lst_ans = d;

		if (a == d) {
			if (d) ans1 = ans2;
			else ans2 = ans1;
			ans2 ^= (1 << i);
			continue;
		}

		int tans1 = ((d ? ans2 : ans1) ^ (b << i)); // 0101
		int tans2 = ((a ? ans2 : ans1) ^ (c << i)); // 1010
		ans1 = tans1, ans2 = tans2;
	}
}

pair<int, int> decode(int N) {
	int ans1 = 0, ans2 = 1, lst = -1, lst_ans = -1;
	for (int i = 1; i < LOG; i++) {
		if (ans2 < ans1) swap(ans1, ans2);

		if (ans1 == ans2) {
			ans2 ^= (1 << i);
			continue;
		}

		int x = f(ans1 ^ ans2);
		int a = (lst == x ? lst_ans : receive()), b = receive(), c = receive();
		lst = i;
		lst_ans = c;

		if (b == c) {
			ans1 ^= (b << i);
			ans2 ^= (b << i);
			continue;
		}

		int d = receive();
		lst = x;
		lst_ans = d;

		if (a == d) {
			if (d) ans1 = ans2;
			else ans2 = ans1;
			ans2 ^= (1 << i);
			continue;
		}

		int tans1 = ((d ? ans2 : ans1) ^ (b << i)); // 0101
		int tans2 = ((a ? ans2 : ans1) ^ (c << i)); // 1010
		ans1 = tans1, ans2 = tans2;
	}

	if (ans1 <= 0 || ans1 > N) ans1 = 1;
	if (ans2 <= 0 || ans2 > N) ans2 = 1;
	return {ans1, ans2};
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 1712 KB Output is correct
2 Correct 120 ms 1740 KB Output is correct
3 Correct 185 ms 1724 KB Output is correct
4 Correct 78 ms 1664 KB Output is correct
5 Correct 93 ms 1676 KB Output is correct
6 Correct 275 ms 1668 KB Output is correct
7 Correct 537 ms 1728 KB Output is correct

Subtask #2
59.00003 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 677 ms 1816 KB Output is partially correct
2 Partially correct 336 ms 1760 KB Output is partially correct
3 Partially correct 400 ms 1868 KB Output is partially correct
4 Partially correct 689 ms 1664 KB Output is partially correct
5 Partially correct 484 ms 1728 KB Output is partially correct
6 Partially correct 492 ms 1708 KB Output is partially correct
7 Partially correct 1975 ms 1740 KB Output is partially correct
8 Partially correct 2842 ms 2068 KB Output is partially correct
9 Partially correct 2244 ms 1904 KB Output is partially correct
10 Partially correct 2276 ms 1892 KB Output is partially correct
11 Partially correct 2375 ms 1956 KB Output is partially correct
12 Partially correct 2290 ms 1908 KB Output is partially correct
13 Partially correct 2454 ms 1944 KB Output is partially correct
14 Partially correct 2312 ms 1944 KB Output is partially correct
15 Partially correct 1262 ms 1832 KB Output is partially correct
16 Partially correct 3052 ms 1916 KB Output is partially correct
17 Partially correct 561 ms 1796 KB Output is partially correct
18 Correct 710 ms 1888 KB Output is correct
19 Partially correct 737 ms 1740 KB Output is partially correct
20 Correct 718 ms 1872 KB Output is correct
21 Correct 784 ms 1732 KB Output is correct
22 Partially correct 785 ms 1796 KB Output is partially correct
23 Partially correct 1068 ms 1800 KB Output is partially correct
24 Correct 55 ms 1704 KB Output is correct
25 Correct 114 ms 1688 KB Output is correct
26 Correct 156 ms 1664 KB Output is correct
27 Correct 84 ms 1824 KB Output is correct
28 Correct 93 ms 1600 KB Output is correct
29 Correct 268 ms 1736 KB Output is correct
30 Correct 718 ms 1664 KB Output is correct