Submission #578464

#	Time	Username	Problem	Language	Result	Execution time	Memory
578464		8e7	Flight to the Ford (BOI22_communication)	C++17	15 / 100	40 ms	1916 KiB

communication

//Challenge: Accepted
#include"communication.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...); }
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);

int st = 1;
int se[16];
int str[4] = {0, 6, 9, 15};
int xo[8] = {0, 1, 2, 4, 5, 8, 9, 10};
void init() {
	for (int i = 0;i < 4;i++) {
		for (int j = 0;j < 8;j++) {
			se[str[i] ^ xo[j]] |= 1<<i;
		}
	}
	//for (int i = 0;i < 16;i++) assert(__builtin_popcount(se[i]) == 2);
}

int getlen(vector<pii> t) {
	int ret = 0;
	for (auto p:t) ret += p.ss - p.ff + 1;
	return ret;
}
vector<vector<pii> > split(vector<pii> t) {
	int len = (getlen(t) + 3) / 4;	
	int cur = 0;
	vector<vector<pii> > ret;
	vector<pii> v;
	for (int i = 0;i < t.size();i++) {
		pii p = t[i];
		//debug("split", p.ff, p.ss);
		int l = p.ss - p.ff + 1;
		if (cur + l <= len) {
			v.push_back(p);
			cur += l;
			if (cur == len) {
				ret.push_back(v);
				cur = 0;
				v.clear();
			}
		} else {
			v.push_back({p.ff, p.ff + len - cur - 1});
			cur = 0;
			ret.push_back(v);
			v.clear();

			t[i].ff += len - cur;
			i--;
		}
	}
	if (v.size()) {
		ret.push_back(v);
		v.clear();
	}
	while (ret.size() < 4) ret.push_back(v);
	return ret;
}
void encode(int N, int X) {
	if (st) {
		st = 0;
		init();
	}

	vector<pii> t;
	t.push_back({1, N});
	while (getlen(t) > 2) {
		//debug("t");
		//for (auto p:t) debug(p.ff, p.ss);
		//debug();
		vector<vector<pii> > s = split(t);
		int p = 0, r = 0, id = 0;
		for (int i = 0;i < 4;i++) {
			//for (auto j:s[i]) debug(j.ff, j.ss);
			//debug();
			assert(s[i].size() > 0);
			int mi = s[i][0].ff, ma = s[i].back().ss;	
			if (mi <= X && X <= ma) {
				id = i;
				p = str[i];
				break;
			}
		}
		//debug(id);
		for (int i = 0;i < 4;i++) {
			r += (1<<i) * send((p >> i) & 1);
		}
		r = se[r];
		vector<pii> to;
		for (int i = 0;i < 4;i++) {
			if (((r >> i) & 1)) {
				to.insert(to.end(), s[i].begin(), s[i].end());
			}
		}
		t = to;
	}
}

std::pair<int, int> decode(int N) {
	if (st) {
		st = 0;
		init();
	}

	vector<pii> t;
	t.push_back({1, N});
	while (getlen(t) > 2) {
		/*
		debug("t");
		for (auto p:t) debug(p.ff, p.ss);
		debug();
		*/

		vector<vector<pii> > s = split(t);
		int r = 0;	
		for (int i = 0;i < 4;i++) {
			r += (1<<i) * receive();
		}
		//debug(r);
		r = se[r];
		vector<pii> to;
		for (int i = 0;i < 4;i++) {
			if (((r >> i) & 1)) {
				//debug(i);
				to.insert(to.end(), s[i].begin(), s[i].end());
			}
		}
		t = to;
	}
    return {t[0].ff, t.back().ss};
}

Compilation message (stderr)

communication.cpp: In function 'std::vector<std::vector<std::pair<int, int> > > split(std::vector<std::pair<int, int> >)':
communication.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for (int i = 0;i < t.size();i++) {
      |                 ~~^~~~~~~~~~
communication.cpp: In function 'void encode(int, int)':
communication.cpp:87:21: warning: variable 'id' set but not used [-Wunused-but-set-variable]
   87 |   int p = 0, r = 0, id = 0;
      |                     ^~

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