Submission #1004873

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004873		LucaDantas	Flight to the Ford (BOI22_communication)	C++17	100 / 100	2565 ms	4388 KiB

communication

#include"communication.h"
#include <bits/stdc++.h>
using namespace std;

struct Range {
	int l, r;
	Range(int l, int r) : l(l), r(r) {}
	int size() { return r - l + 1; }
	pair<Range, Range> split(int qtd) {
		return {Range(l, l + qtd - 1), Range(l + qtd, r) };
	}
	friend ostream& operator<<(ostream& os, const Range& r) {
		return os << '<' <<r.l << ", " << r.r << '>';
	}

};

int get_total_size(vector<Range> ranges) {
	int ans = 0;
	for(Range r : ranges)
		ans += r.size();
	return ans;
}

pair<vector<Range>, vector<Range>> split(vector<Range> ranges) {
	int sz = get_total_size(ranges);
	vector<Range> g[2];

	int now = 0;
	for(Range r : ranges) {
		if(now + r.size() <= (sz+1)/2)
			g[0].push_back(r), now += r.size();
		else if(now < (sz+1)/2) {
			auto [r1, r2] = r.split((sz+1)/2 - now);
			g[0].push_back(r1);
			g[1].push_back(r2);
			now = (sz+1)/2;
		} else
			g[1].push_back(r);
	}
	return {g[0], g[1]};
}

pair<int,int> answer(vector<Range> ranges) {
	vector<int> ans;
	for(Range r : ranges)
		for(int i = r.l; i <= r.r; i++)
			ans.push_back(i);
	return {ans[0], ans[1]};
}


pair<int,int> build_decode(vector<Range> head, vector<Range> left, vector<Range> right) {
	if(get_total_size(head) <= 2 && !get_total_size(left) && !get_total_size(right))
		return answer(head);
	if(get_total_size(head) <= 1 && get_total_size(left) <= 1 && get_total_size(right) <= 1) {
		if(!receive())
			return {head[0].l, left[0].l};
		else
			return {head[0].l, right[0].l};
	}
	if(get_total_size(head) <= 2 && get_total_size(left) <= 1 && !get_total_size(right)) {
		if(receive() == 1)
			return answer(head);

		if(receive() == 0)
			return {head[0].l, left[0].l};
		else if(head.size() == 2)
			return {head[1].l, left[0].l};
		else
			return {head[0].r, left[0].l};

	}

	// assumes there is always the same number of people on the left and right
	int n = (int)head.size();
	vector<Range> g[2];
	pair<vector<Range>, vector<Range>> spl = split(head);
	g[0] = spl.first;
	g[1] = spl.second;

	if(get_total_size(left) > get_total_size(right))
		swap(g[0], g[1]);
	
	int k = receive();
	vector<Range> &pre = k ? right : left;

	spl = split(g[!k]);
	int m = g[!k].size();
	vector<Range> f1 = spl.first;
	vector<Range> f2 = spl.second;

	g[k].insert(g[k].end(), pre.begin(), pre.end());

	return build_decode(g[k], f1, f2);
}

bool in(vector<Range> ranges, int x) {
	for(Range r : ranges)
		if(r.l <= x && x <= r.r)
			return true;
	return false;
}

void build_encode(vector<Range> head, vector<Range> left, vector<Range> right, int secret) {
	if(get_total_size(head) <= 2 && !get_total_size(left) && !get_total_size(right))
		return;
	if(get_total_size(head) <= 1 && get_total_size(left) <= 1 && get_total_size(right) <= 1) {
		if(in(left, secret))
			send(0);
		else // se tiver em left ou right signifca que deu errado antes entao to garantido
			send(1); // se tiver em head nao importa
		return;
	}
	if(get_total_size(head) <= 2 && get_total_size(left) <= 1 && !get_total_size(right)) {
		if(in(left, secret)) {
			send(0), send(0); // so importa que vou pra esquerda agr, dps fds
			return;
		} else {
			int nxt = send(1);
			if(nxt) return; // fui pra direita entao ja posso terminar

			if(head[0].l == secret)
				send(0);
			else
				send(1);

			return;
		}

	}

	// assumes there is always the same number of people on the left and right
	int n = (int)head.size();
	vector<Range> g[2];
	pair<vector<Range>, vector<Range>> spl = split(head);
	g[0] = spl.first;
	g[1] = spl.second;

	if(get_total_size(left) > get_total_size(right))
		swap(g[0], g[1]);
	
	int k;
	if(in(left, secret)) {
		k = 0;
		send(0); // anterior foi mudado entao garanto movimento aqui
	} else if(in(right, secret)) {
		k = 1;
		send(1); // anterior foi mudado entao garanto movimento aqui
	} else {
		int tento = in(g[1], secret);
		k = send(tento); // tento ir pra aquele lado mas se nao for tenho que mover pro outro
	}

	vector<Range> &pre = k ? right : left;

	spl = split(g[!k]);
	int m = g[!k].size();
	vector<Range> f1 = spl.first;
	vector<Range> f2 = spl.second;

	g[k].insert(g[k].end(), pre.begin(), pre.end());

	build_encode(g[k], f1, f2, secret);
}



void encode(int N, int X) {
	vector<Range> a = {Range(1, N)};
	vector<int> s;
	return build_encode(a, {}, {}, X);
}

std::pair<int, int> decode(int N) {
	vector<Range> a = {Range(1, N)};
	vector<int> s;
	return build_decode(a, {}, {});
}

Compilation message (stderr)

communication.cpp: In function 'std::pair<int, int> build_decode(std::vector<Range>, std::vector<Range>, std::vector<Range>)':
communication.cpp:76:6: warning: unused variable 'n' [-Wunused-variable]
   76 |  int n = (int)head.size();
      |      ^
communication.cpp:89:6: warning: unused variable 'm' [-Wunused-variable]
   89 |  int m = g[!k].size();
      |      ^
communication.cpp: In function 'void build_encode(std::vector<Range>, std::vector<Range>, std::vector<Range>, int)':
communication.cpp:134:6: warning: unused variable 'n' [-Wunused-variable]
  134 |  int n = (int)head.size();
      |      ^
communication.cpp:158:6: warning: unused variable 'm' [-Wunused-variable]
  158 |  int m = g[!k].size();
      |      ^

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