oj.uz

Submission #672547

# Submission time Handle Problem Language Result Execution time Memory
672547 2022-12-16T14:44:11 Z LittleCube Flight to the Ford (BOI22_communication) C++17
100 / 100
 3104 ms 2628 KB 
#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 + 1) / 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;
	}
}
/*
3 1 -> [2 1] [1+1 2]
2 2 -> [1 1] [1 1]
*/

pii divide(state s, int x, bool encode, int dep = 1)
{
	assert(dep <= 150);
	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(encode ? 0 : 1);
		for (auto [l, r] : B)
			for (int i = l; i <= r; i++)
				v.emplace_back(i);
		while (v.size() < 3)
			v.emplace_back(encode ? 0 : 1);
		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, dep + 1);
	else
		return divide(R, x, encode, dep + 1);
}

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 10 ms 1784 KB Output is correct
2 Correct 11 ms 1748 KB Output is correct
3 Correct 15 ms 1724 KB Output is correct
4 Correct 13 ms 1768 KB Output is correct
5 Correct 13 ms 1744 KB Output is correct
6 Correct 21 ms 1788 KB Output is correct
7 Correct 47 ms 1668 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 583 ms 1868 KB Output is correct
2 Correct 334 ms 1816 KB Output is correct
3 Correct 443 ms 1852 KB Output is correct
4 Correct 727 ms 2024 KB Output is correct
5 Correct 611 ms 1860 KB Output is correct
6 Correct 519 ms 1896 KB Output is correct
7 Correct 1972 ms 2112 KB Output is correct
8 Correct 3104 ms 2628 KB Output is correct
9 Correct 2409 ms 2440 KB Output is correct
10 Correct 2703 ms 2476 KB Output is correct
11 Correct 2681 ms 2400 KB Output is correct
12 Correct 2563 ms 2332 KB Output is correct
13 Correct 2610 ms 2400 KB Output is correct
14 Correct 2651 ms 2380 KB Output is correct
15 Correct 1287 ms 2096 KB Output is correct
16 Correct 3101 ms 2344 KB Output is correct
17 Correct 775 ms 2244 KB Output is correct
18 Correct 738 ms 2104 KB Output is correct
19 Correct 821 ms 2032 KB Output is correct
20 Correct 760 ms 2108 KB Output is correct
21 Correct 803 ms 2100 KB Output is correct
22 Correct 905 ms 2044 KB Output is correct
23 Correct 1288 ms 2272 KB Output is correct
24 Correct 8 ms 1684 KB Output is correct
25 Correct 8 ms 1780 KB Output is correct
26 Correct 15 ms 1796 KB Output is correct
27 Correct 14 ms 1636 KB Output is correct
28 Correct 15 ms 1744 KB Output is correct
29 Correct 26 ms 1724 KB Output is correct
30 Correct 42 ms 1784 KB Output is correct