oj.uz

답안 #668220

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
668220 2022-12-03T10:37:12 Z Sohsoh84 Flight to the Ford (BOI22_communication) C++17
0 / 100
 276 ms 200 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 rng() % 2 ? 31 - __builtin_clz(x) : __builtin_ctz(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
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 46 ms 200 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 276 ms 200 KB Not correct
2 Halted 0 ms 0 KB -