Submission #584207

#	Time	Username	Problem	Language	Result	Execution time	Memory
584207		8e7	Flight to the Ford (BOI22_communication)	C++17	15 / 100	433 ms	1896 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;
		}
	}
}

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) + 1) / 2;	
	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});
			t[i].ff += len - cur;
			i--;
			cur = 0;
			ret.push_back(v);
			v.clear();
		}
	}
	if (v.size()) {
		ret.push_back(v);
		v.clear();
	}
	while (ret.size() < 2) ret.push_back(v);
	return ret;
}
vector<pii> merge(vector<pii> &s, vector<pii> &t) {
	vector<pii> ret;
	int ind = 0;
	for (int i = 0;i < s.size();i++) {
		while (ind < t.size() && t[ind].ff < s[i].ff) ret.push_back(t[ind++]);
		ret.push_back(s[i]);
	}
	while (ind < t.size()) ret.push_back(t[ind++]);
	return ret;
}
bool in(int x, vector<pii> &s) {
	for (auto p:s) {
		if (p.ff <= x && x <= p.ss) return 1;
	}
	return 0;
}
void encode(int N, int X) {
	if (st) {
		st = 0;
		init();
	}

	vector<pii> A, B;
	A.push_back({1, N});
	while (getlen(A) + getlen(B) > 3) {
		vector<vector<pii> > sa = split(A), sb = split(B);
		int ask = 0;
		if (in(X, sb[1])) ask = 1;
		int res = send(ask);
		if (res == 0) {
			A = merge(sa[0], sb[0]);
			B = sa[1];
		} else {
			A = merge(sa[1], sb[1]);
			B = sa[0];
		}
	}
		
	vector<pii> t = merge(A, B);
	if (getlen(t) == 3) {
		int enc = 1;
		if (X == t[0].ff) enc = 0;
		else if (X == t.back().ss) enc = 2;		
		for (int i = 0;i < 4;i++) send((str[enc] >>i)&1);
	}
}

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

	vector<pii> A, B;
	A.push_back({1, N});
	while (getlen(A) + getlen(B) > 3) {
		vector<vector<pii> > sa = split(A), sb = split(B);
		int res = receive();
		if (res == 0) {
			A = merge(sa[0], sb[0]);
			B = sa[1];
		} else {
			A = merge(sa[1], sb[1]);
			B = sa[0];
		}
	}
	vector<pii> t = merge(A, B);
	if (getlen(t) == 3) {
		vector<int> num, ans;
		for (auto p:t) {
			for (int j = p.ff;j <= p.ss;j++) num.push_back(j);
		}
		int s = 0;
		for (int i = 0;i < 4;i++) s += (1<<i) * receive();
		for (int i = 0;i < 3;i++) {
			if ((se[s]>>i)&1) ans.push_back(num[i]); 	
		}
		return {ans[0], ans.back()};
	} else {
    	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:44: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]
   44 |  for (int i = 0;i < t.size();i++) {
      |                 ~~^~~~~~~~~~
communication.cpp: In function 'std::vector<std::pair<int, int> > merge(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&)':
communication.cpp:75: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]
   75 |  for (int i = 0;i < s.size();i++) {
      |                 ~~^~~~~~~~~~
communication.cpp:76:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   while (ind < t.size() && t[ind].ff < s[i].ff) ret.push_back(t[ind++]);
      |          ~~~~^~~~~~~~~~
communication.cpp:79:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  while (ind < t.size()) ret.push_back(t[ind++]);
      |         ~~~~^~~~~~~~~~

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