oj.uz

Submission #869363

# Submission time Handle Problem Language Result Execution time Memory
869363 2023-11-04T08:10:08 Z Trisanu_Das Flight to the Ford (BOI22_communication) C++17
100 / 100
 2392 ms 5008 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;
};
 
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;
	}
}
 
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;
	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 6 ms 3208 KB Output is correct
2 Correct 6 ms 2768 KB Output is correct
3 Correct 6 ms 2796 KB Output is correct
4 Correct 8 ms 2676 KB Output is correct
5 Correct 4 ms 3136 KB Output is correct
6 Correct 12 ms 2844 KB Output is correct
7 Correct 19 ms 2908 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 3692 KB Output is correct
2 Correct 193 ms 3572 KB Output is correct
3 Correct 235 ms 3632 KB Output is correct
4 Correct 433 ms 3432 KB Output is correct
5 Correct 380 ms 3700 KB Output is correct
6 Correct 345 ms 3260 KB Output is correct
7 Correct 1329 ms 4412 KB Output is correct
8 Correct 2147 ms 5008 KB Output is correct
9 Correct 1757 ms 4152 KB Output is correct
10 Correct 1727 ms 4832 KB Output is correct
11 Correct 1762 ms 4484 KB Output is correct
12 Correct 1909 ms 4616 KB Output is correct
13 Correct 2201 ms 4588 KB Output is correct
14 Correct 2179 ms 3868 KB Output is correct
15 Correct 1158 ms 3704 KB Output is correct
16 Correct 2392 ms 4128 KB Output is correct
17 Correct 597 ms 4408 KB Output is correct
18 Correct 625 ms 4024 KB Output is correct
19 Correct 589 ms 3864 KB Output is correct
20 Correct 576 ms 3756 KB Output is correct
21 Correct 602 ms 3460 KB Output is correct
22 Correct 599 ms 3580 KB Output is correct
23 Correct 970 ms 3556 KB Output is correct
24 Correct 12 ms 3196 KB Output is correct
25 Correct 4 ms 2792 KB Output is correct
26 Correct 11 ms 2756 KB Output is correct
27 Correct 7 ms 2740 KB Output is correct
28 Correct 10 ms 2960 KB Output is correct
29 Correct 13 ms 3096 KB Output is correct
30 Correct 20 ms 3196 KB Output is correct