oj.uz

Submission #668215

# Submission time Handle Problem Language Result Execution time Memory
668215 2022-12-03T10:24:04 Z Sohsoh84 Flight to the Ford (BOI22_communication) C++17
74 / 100
 2899 ms 2016 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;

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

void encode(int N, int X) {
	int ans1 = 0, ans2 = 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 = send((X >> x) & 1), b = send((X >> i) & 1), c = send((X >> i) & 1);
		if (b == c) {
			ans1 ^= (b << i);
			ans2 ^= (b << i);
			continue;
		}

		int d = send((X >> x) & 1);
		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;
	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 = receive(), b = receive(), c = receive();
		if (b == c) {
			ans1 ^= (b << i);
			ans2 ^= (b << i);
			continue;
		}

		int d = receive();
		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};
}

Compilation message

communication.cpp: In function 'std::pair<int, int> decode(int)':
communication.cpp:65:7: warning: unused variable 'x' [-Wunused-variable]
   65 |   int x = f(ans1 ^ ans2);
      |       ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 1704 KB Output is correct
2 Correct 106 ms 1720 KB Output is correct
3 Correct 169 ms 1644 KB Output is correct
4 Correct 88 ms 1740 KB Output is correct
5 Correct 92 ms 1776 KB Output is correct
6 Correct 261 ms 1856 KB Output is correct
7 Correct 623 ms 1716 KB Output is correct

Subtask #2
59.00003 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 796 ms 1696 KB Output is partially correct
2 Partially correct 337 ms 1780 KB Output is partially correct
3 Partially correct 483 ms 1776 KB Output is partially correct
4 Partially correct 718 ms 1800 KB Output is partially correct
5 Partially correct 587 ms 1724 KB Output is partially correct
6 Partially correct 572 ms 1720 KB Output is partially correct
7 Partially correct 1968 ms 1884 KB Output is partially correct
8 Partially correct 2899 ms 1940 KB Output is partially correct
9 Partially correct 2881 ms 1800 KB Output is partially correct
10 Partially correct 2196 ms 1876 KB Output is partially correct
11 Partially correct 2578 ms 1796 KB Output is partially correct
12 Partially correct 2609 ms 1880 KB Output is partially correct
13 Partially correct 2643 ms 1840 KB Output is partially correct
14 Partially correct 2529 ms 2016 KB Output is partially correct
15 Partially correct 1234 ms 1792 KB Output is partially correct
16 Partially correct 2827 ms 1744 KB Output is partially correct
17 Partially correct 657 ms 1832 KB Output is partially correct
18 Correct 535 ms 1820 KB Output is correct
19 Partially correct 690 ms 1736 KB Output is partially correct
20 Correct 631 ms 1752 KB Output is correct
21 Correct 766 ms 1784 KB Output is correct
22 Partially correct 831 ms 1744 KB Output is partially correct
23 Partially correct 1108 ms 1808 KB Output is partially correct
24 Correct 58 ms 1712 KB Output is correct
25 Correct 52 ms 1664 KB Output is correct
26 Correct 160 ms 1664 KB Output is correct
27 Correct 52 ms 1760 KB Output is correct
28 Correct 107 ms 1776 KB Output is correct
29 Correct 276 ms 1760 KB Output is correct
30 Correct 681 ms 1668 KB Output is correct