Submission #654727

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
654727	2022-11-01T11:31:09 Z	prvocislo	Flight to the Ford (BOI22_communication)	C++17	100 / 100	3420 ms	1948 KB

communication

#include"communication.h"
#include <algorithm>
#include <iostream>
#include <vector>
typedef long long ll;
using namespace std;

struct segment { int l, r; };
bool cmp(segment a, segment b)
{
	return a.l < b.l;
}
int siz(const vector<segment>& v)
{
	int sum = 0;
	for (segment i : v) sum += i.r - i.l + 1;
	return sum;
}
int kth(const vector<segment> &v, int k) // k-ty prvok ktory mame (1-indexovane)
{
	for (segment i : v)
	{
		if (i.l + k - 1 <= i.r) return i.l + k - 1;
		k -= (i.r - i.l + 1);
	}
	return 1e9 + 5;
}
vector<segment> sub(const vector<segment>& v, int l, int r) // zober len prvky l az r
{
	vector<segment> nw;
	for (segment i : v)
	{
		if (i.r < l || i.l > r) continue;
		nw.push_back({ max(i.l, l), min(i.r, r) });
	}
	return nw;
}
vector<segment> add(const vector<segment>& a, const vector<segment>& b)
{
	vector<segment> v;
	for (segment i : a) v.push_back(i);
	for (segment i : b) v.push_back(i);
	sort(v.begin(), v.end(), cmp);
	return v;
}
bool contains(const vector<segment>& v, int x)
{
	for (segment i : v) if (i.l <= x && x <= i.r) return true;
	return false;
}
void encode(int n, int x) 
{
	vector<segment> v = { {1,n} }, p; // vsetky, tie co uz musia hovorit pravdu
	while (true)
	{
		int nv = siz(v), np = siz(p);
		if (nv + np < 4) break;
		int sv = nv - nv / 2, sp = np / 2;
		vector<segment> v1 = sub(v, 1, kth(v, sv)), v0 = sub(v, kth(v, sv + 1), kth(v, nv));
		vector<segment> p1 = sub(p, 1, kth(p, sp)), p0 = sub(p, kth(p, sp + 1), kth(p, np));
		int ans = send(contains(v1, x) || contains(p1, x));
		if (ans == 1) v = add(v1, p1), p = v0;
		if (ans == 0) v = add(v0, p0), p = v1;
	}
	v = add(v, p);
	int S = siz(v);
	if (S < 3) return;
	int sent = -1;
	if (kth(v, 1) == x) sent = send(1);
	else sent = send(0);
	if (sent == 0)
	{
		int sent = -1;
		if (kth(v, 1) == x) sent = send(1);
		else sent = send(0);
		if (sent == 1) send(kth(v, 2) == x);
	}
	else send(kth(v, 2) == x);
}
pair<int, int> decode(int n) 
{
	vector<segment> v = { {1,n} }, p;
	while (true)
	{
		int nv = siz(v), np = siz(p);
		if (nv + np < 4) break;
		int sv = nv - nv / 2, sp = np / 2;
		vector<segment> v1 = sub(v, 1, kth(v, sv)), v0 = sub(v, kth(v, sv + 1), kth(v, nv));
		vector<segment> p1 = sub(p, 1, kth(p, sp)), p0 = sub(p, kth(p, sp + 1), kth(p, np));
		int ans = receive();
		if (ans == 1) v = add(v1, p1), p = v0;
		if (ans == 0) v = add(v0, p0), p = v1;
	}
	v = add(v, p);
	vector<int> a = { kth(v,1), kth(v,2), kth(v,3) };
	if (receive()) return receive() ? make_pair(a[0], a[1]) : make_pair(a[0], a[2]);
	if (receive()) return receive() ? make_pair(a[0], a[1]) : make_pair(a[0], a[2]);
	else return make_pair(a[1], a[2]);
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	1756 KB	Output is correct
2	Correct	7 ms	1716 KB	Output is correct
3	Correct	8 ms	1800 KB	Output is correct
4	Correct	6 ms	1636 KB	Output is correct
5	Correct	7 ms	1604 KB	Output is correct
6	Correct	18 ms	1828 KB	Output is correct
7	Correct	23 ms	1744 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	661 ms	1664 KB	Output is correct
2	Correct	283 ms	1680 KB	Output is correct
3	Correct	435 ms	1688 KB	Output is correct
4	Correct	689 ms	1736 KB	Output is correct
5	Correct	651 ms	1816 KB	Output is correct
6	Correct	558 ms	1736 KB	Output is correct
7	Correct	1934 ms	1852 KB	Output is correct
8	Correct	3420 ms	1868 KB	Output is correct
9	Correct	2918 ms	1896 KB	Output is correct
10	Correct	2879 ms	1860 KB	Output is correct
11	Correct	2909 ms	1884 KB	Output is correct
12	Correct	2755 ms	1948 KB	Output is correct
13	Correct	2655 ms	1792 KB	Output is correct
14	Correct	2779 ms	1896 KB	Output is correct
15	Correct	1358 ms	1912 KB	Output is correct
16	Correct	3086 ms	1856 KB	Output is correct
17	Correct	777 ms	1808 KB	Output is correct
18	Correct	785 ms	1784 KB	Output is correct
19	Correct	798 ms	1872 KB	Output is correct
20	Correct	715 ms	1752 KB	Output is correct
21	Correct	735 ms	1780 KB	Output is correct
22	Correct	793 ms	1784 KB	Output is correct
23	Correct	1240 ms	1784 KB	Output is correct
24	Correct	8 ms	1736 KB	Output is correct
25	Correct	12 ms	1788 KB	Output is correct
26	Correct	13 ms	1816 KB	Output is correct
27	Correct	10 ms	1724 KB	Output is correct
28	Correct	11 ms	1680 KB	Output is correct
29	Correct	18 ms	1852 KB	Output is correct
30	Correct	34 ms	1740 KB	Output is correct