Submission #654727

#	Time	Username	Problem	Language	Result	Execution time	Memory
654727		prvocislo	Flight to the Ford (BOI22_communication)	C++17	100 / 100	3420 ms	1948 KiB

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 / 15
• Subtask 2: 85 / 85