Submission #654496

#	Time	Username	Problem	Language	Result	Execution time	Memory
654496		prvocislo	Flight to the Ford (BOI22_communication)	C++17	49 / 100	4186 ms	2080 KiB

communication

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

struct segment
{
	int l, r;
};
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);
	}
}
vector<segment> excl(const vector<segment>& v, int l, int r) // vynechaj prvky l az r
{
	vector<segment> nw;
	for (segment i : v)
	{
		if (i.l <= l - 1) nw.push_back({ i.l, min(i.r, l - 1) });
		if (i.r >= r + 1) nw.push_back({ max(i.l, r + 1), i.r });
	}
	return nw;
}
vector<segment> skip(const vector<segment>& v, vector<int> s, int a0, int a1)
{
	int num = a0 * 2 + a1, l = 1, r = 0;
	for (int i = 0; i < num; i++) l += s[i];
	for (int i = 0; i <= num; i++) r += s[i];
	return excl(v, kth(v, l), kth(v, r));
}
void encode(int n, int x) 
{
	vector<segment> v = { {1,n} };
	while (true)
	{
		int S = siz(v);
		if (S < 4) break;
		vector<int> s(4, 0);
		for (int i = 0; i < 4; i++) s[i] = S / 4 + (i < S % 4);
		// opytame sa na [0, 1] a [0, 2]
		int pos = 0, sum = 0;
		for (int i = 0; i < 4; i++)
		{
			sum += s[i];
			if (kth(v, sum) < x) pos++;
		}
		int a0, a1;
		a0 = send(pos >> 1);
		a1 = send(pos & 1);
		v = skip(v, s, a0 ^ 1, a1 ^ 1);
	}
	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} };
	while (true)
	{
		int S = siz(v);
		if (S < 4) break;
		vector<int> s(4, 0);
		for (int i = 0; i < 4; i++) s[i] = S / 4 + (i < S % 4);
		// opytame sa na [0, 1] a [0, 2]
		int a0 = receive(), a1 = receive();
		v = skip(v, s, a0 ^ 1, a1 ^ 1);
	}
	vector<int> p = { kth(v,1), kth(v,2), kth(v,3) };
	if (receive()) return receive() ? make_pair(p[0], p[1]) : make_pair(p[0], p[2]);
	if (receive()) return receive() ? make_pair(p[0], p[1]) : make_pair(p[0], p[2]);
	else return make_pair(p[1], p[2]);
}

Compilation message (stderr)

communication.cpp: In function 'int kth(const std::vector<segment>&, int)':
communication.cpp:29:1: warning: control reaches end of non-void function [-Wreturn-type]
   29 | }
      | ^

• Subtask 1: 15 / 15
• Subtask 2: 34 / 85