Submission #668225

#	Time	Username	Problem	Language	Result	Execution time	Memory
668225		Sohsoh84	Flight to the Ford (BOI22_communication)	C++17	90 / 100	2708 ms	2076 KiB

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 / 15
• Subtask 2: 75.000005 / 85