Submission #668618

#	Time	Username	Problem	Language	Result	Execution time	Memory
668618		wakaka	Flight to the Ford (BOI22_communication)	C++17	100 / 100	6965 ms	2388 KiB

communication

#include "communication.h"
#include <bits/stdc++.h>
using namespace std;
//
// --- 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
//
bool split(set<array<int, 2>>& s, int p) {
	if (p == INT_MIN) return false;
	auto it = s.lower_bound({p, p - 1}); // Use p-1 to handle array<int, >= 2> case.
	if (it == s.begin()) return false;
	--it;
	auto cur = *it;
	assert(cur[0] < p);
	if (cur[1] < p) return false;
	s.erase(it);
	auto l = cur;
	l[1] = p - 1;
	s.insert(l); // {cur[0], p - 1, cur[2...]}
	auto r = cur;
	r[0] = p;
	s.insert(r); // {p, cur[1], cur[2...]}
	return true;
}

template <typename F>
pair<int, int> protocol(int n, F&& getBitReceived) {
	const int SMALL = 50;
	const int INF = 1e9;
	vector<vector<int>> dp(SMALL, vector<int>(SMALL, INF));
	vector<vector<array<int, 2>>> move(SMALL, vector<array<int, 2>>(SMALL));
	for (int s = 0; s < SMALL; ++s)
		for (int a = 0; a <= s; ++a) {
			int b = s - a;
			if (s <= 2) {
				dp[a][b] = 0;
				continue;
			}
			for (int a0 = 0; a0 <= a; ++a0)
				for (int b0 = 0; b0 <= b; ++b0) {
					if (a != a0 && b != b0) assert(dp[a0][b0] <= dp[a][b]);
					// Note we ignore a' + b' == a + b and a' >= a to prevent cycles,
					// but that's OK since it is not needed to consider those. (no proof, so dp[a][b] may not be optimal)
					int v = max(dp[a0 + b0][a - a0], dp[s - a0 - b0][a0]) + 1;
					if (v < dp[a][b]) {
						dp[a][b] = v;
						move[a][b] = {a0, b0};
					}
				}
			assert(dp[a][b] < INF);
		}
	set<array<int, 2>> lastTrue, lastFalse;
	lastTrue.insert({1, n});
	int a = n, b = 0;
	while (a + b > 2) {
		int a0 = a / 2, b0 = b / 2;
		if (a + b < move.size()) {
			a0 = move[a][b][0];
			b0 = move[a][b][1];
		}
		auto findKthPoint = [&](const set<array<int, 2>>& s, int k) {
			for (auto& i : s) {
				if (i[1] - i[0] + 1 >= k) {
					return i[0] + k - 1;
				}
				k -= i[1] - i[0] + 1;
			}
			return 0;
		};
		int p0 = findKthPoint(lastTrue, a0);
		split(lastTrue, p0 + 1);
		set<array<int, 2>> T0, T1, F0, F1;
		for (auto& i : lastTrue)
			if (i[1] <= p0) T0.insert(i);
			else T1.insert(i);
		int q0 = findKthPoint(lastFalse, b0);
		split(lastFalse, q0 + 1);
		for (auto& i : lastFalse)
			if (i[1] <= q0) F0.insert(i);
			else F1.insert(i);
		auto S = T0;
		S.insert(F0.begin(), F0.end());
		int bit = getBitReceived(S);
		if (bit == 1) {
			lastTrue = S;
			lastFalse = T1;
		} else {
			lastTrue = T1;
			lastTrue.insert(F1.begin(), F1.end());
			lastFalse = T0;
		}
		a = b = 0;
		for (auto& i : lastTrue) a += i[1] - i[0] + 1;
		for (auto& i : lastFalse) b += i[1] - i[0] + 1;
	}
	auto S = lastTrue;
	S.insert(lastFalse.begin(), lastFalse.end());
	pair<int, int> ret = {-1, -1};
	for (auto& i : S) {
		if (ret.first == -1) ret.first = ret.second = i[0];
		else ret.second = i[0];
		if (i[1] > i[0]) ret.second = i[1];
	}
	return ret;
}

void encode(int N, int X) {
	protocol(N, [&](const set<array<int, 2>>& S) {
		// Returns bit that is received.
		int bit = 0;
		for (auto& i : S) if (i[0] <= X && X <= i[1]) bit = 1;
		return send(bit);
	});
}

pair<int, int> decode(int N) {
	auto possibles = protocol(N, [&](const set<array<int, 2>>& S) {
		// Returns bit that is received.
		return receive();
	});
	return possibles;
}

Compilation message (stderr)

communication.cpp: In instantiation of 'std::pair<int, int> protocol(int, F&&) [with F = encode(int, int)::<lambda(const std::set<std::array<int, 2> >&)>]':
communication.cpp:121:3:   required from here
communication.cpp:65:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::array<int, 2> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   if (a + b < move.size()) {
      |       ~~~~~~^~~~~~~~~~~~~
communication.cpp: In instantiation of 'std::pair<int, int> protocol(int, F&&) [with F = decode(int)::<lambda(const std::set<std::array<int, 2> >&)>]':
communication.cpp:128:3:   required from here
communication.cpp:65:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::array<int, 2> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85