Submission #672534

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
672534	2022-12-16T14:17:08 Z	LittleCube	Flight to the Ford (BOI22_communication)	C++17	15 / 100	1080 ms	2800 KB

communication

#include "communication.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

struct state
{
	int szA = 0, szB = 0;
	vector<pii> A, B;
};

// 11 -> 10 01 11
// 10 -> 10 00 11
// 00 -> 00 01

void split(state &s, state &L, state &R)
{
	auto &[szA, szB, A, B] = s;
	int lA = szA / 2, lB = szB / 2;
	for (auto [l, r] : A)
	{
		if (r - l + 1 <= lA)
			L.A.emplace_back(pii(l, r));
		else if (lA <= 0)
			R.A.emplace_back(pii(l, r));
		else
		{
			L.A.emplace_back(pii(l, l + lA - 1));
			R.A.emplace_back(pii(l + lA, r));
		}
		lA -= r - l + 1;
	}
	R.B = L.A;
	L.B = R.A;
	for (auto [l, r] : B)
	{
		if (r - l + 1 <= lB)
			L.A.emplace_back(pii(l, r));
		else if (lB <= 0)
			R.A.emplace_back(pii(l, r));
		else
		{
			L.A.emplace_back(pii(l, l + lB - 1));
			R.A.emplace_back(pii(l + lB, r));
		}
		lB -= r - l + 1;
	}
}

pii divide(state s, int x, bool encode)
{
	auto &[szA, szB, A, B] = s;
	for (auto [l, r] : A)
		szA += r - l + 1;
	for (auto [l, r] : B)
		szB += r - l + 1;
	cerr << szA << ' ' << szB << '\n';
	// cerr << "divide " << szA << " A ";
	// for(auto [i, j] : A)
	// 	cerr << "[" << i << ", " << j << "] ";
	// cerr << szB << " B ";
	// for(auto [i, j] : B)
	// 	cerr << "[" << i << ", " << j << "] ";
	// cerr << '\n';
	if (szA <= 2 && szB <= 1)
	{
		vector<int> v;
		for (auto [l, r] : A)
			for (int i = l; i <= r; i++)
				v.emplace_back(i);
		while (v.size() < 2)
			v.emplace_back(v[0]);
		for (auto [l, r] : B)
			for (int i = l; i <= r; i++)
				v.emplace_back(i);
		while (v.size() < 3)
			v.emplace_back(v[0]);
		if (encode)
		{

			if (x == v[0])
				send(1), send(1);
			else if (x == v[1])
				send(1), send(0);
			else
				send(0), send(0);
			return pii(0, 0);
		}
		else
		{
			int res = receive() * 2;
			res += receive();
			if (res == 2 || res == 3)
				return pii(v[0], v[1]);
			else if (res == 1)
				return pii(v[0], v[2]);
			else
				return pii(v[1], v[2]);
		}
	}
	state L, R;
	split(s, L, R);
	int signal = 1;
	for (auto [l, r] : L.A)
		if (l <= x && x <= r)
			signal = 0;
	int res;
	if (encode)
		res = send(signal);
	else
		res = receive();

	if (res == 0)
		return divide(L, x, encode);
	else
		return divide(R, x, encode);
}

void encode(int N, int X)
{
	state s;
	s.A.emplace_back(pii(1, N));
	divide(s, X, 1);
}

pii decode(int N)
{
	state s;
	s.A.emplace_back(pii(1, N));
	return divide(s, 0, 0);
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	1900 KB	Output is correct
2	Correct	14 ms	1680 KB	Output is correct
3	Correct	20 ms	1692 KB	Output is correct
4	Correct	14 ms	1620 KB	Output is correct
5	Correct	22 ms	1792 KB	Output is correct
6	Correct	34 ms	1796 KB	Output is correct
7	Correct	56 ms	1744 KB	Output is correct

Subtask #2

0.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1080 ms	2800 KB	Output is correct
2	Incorrect	7 ms	388 KB	Not correct
3	Halted	0 ms	0 KB	-