Submission #668225

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
668225	2022-12-03T10:45:10 Z	Sohsoh84	Flight to the Ford (BOI22_communication)	C++17	90 / 100	2708 ms	2076 KB

communication

#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;

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

void encode(int N, int X) {
	int ans1 = 0, ans2 = (1 << (LOG - 1)), lst = -1, lst_ans = -1;
	for (int i = LOG - 2; i >= 0; 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 << (LOG - 1)), lst = -1, lst_ans = -1;
	for (int i = LOG - 2; i >= 0; 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	54 ms	1712 KB	Output is correct
2	Correct	97 ms	1720 KB	Output is correct
3	Correct	151 ms	1704 KB	Output is correct
4	Correct	74 ms	1664 KB	Output is correct
5	Correct	96 ms	1740 KB	Output is correct
6	Correct	272 ms	1784 KB	Output is correct
7	Correct	528 ms	1768 KB	Output is correct

Subtask #2

75.000005 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	474 ms	1708 KB	Output is partially correct
2	Partially correct	247 ms	1744 KB	Output is partially correct
3	Partially correct	289 ms	1848 KB	Output is partially correct
4	Partially correct	720 ms	1788 KB	Output is partially correct
5	Partially correct	581 ms	1696 KB	Output is partially correct
6	Correct	517 ms	1688 KB	Output is correct
7	Correct	1612 ms	1908 KB	Output is correct
8	Correct	2519 ms	1924 KB	Output is correct
9	Correct	2138 ms	2016 KB	Output is correct
10	Correct	2216 ms	2076 KB	Output is correct
11	Correct	2461 ms	1916 KB	Output is correct
12	Correct	2042 ms	1880 KB	Output is correct
13	Correct	2171 ms	2052 KB	Output is correct
14	Correct	2276 ms	1820 KB	Output is correct
15	Correct	1024 ms	1724 KB	Output is correct
16	Correct	2708 ms	1780 KB	Output is correct
17	Correct	635 ms	1792 KB	Output is correct
18	Correct	624 ms	1852 KB	Output is correct
19	Correct	586 ms	1732 KB	Output is correct
20	Correct	544 ms	1868 KB	Output is correct
21	Correct	584 ms	1792 KB	Output is correct
22	Correct	676 ms	1780 KB	Output is correct
23	Correct	1012 ms	1756 KB	Output is correct
24	Correct	96 ms	1712 KB	Output is correct
25	Correct	132 ms	1676 KB	Output is correct
26	Correct	101 ms	1776 KB	Output is correct
27	Correct	78 ms	1712 KB	Output is correct
28	Correct	74 ms	1804 KB	Output is correct
29	Correct	246 ms	1880 KB	Output is correct
30	Correct	509 ms	1684 KB	Output is correct