oj.uz

Submission #578467

# Submission time Handle Problem Language Result Execution time Memory
578467 2022-06-17T03:22:19 Z 8e7 Flight to the Ford (BOI22_communication) C++17
74 / 100
 3909 ms 1960 KB 
//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});
			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() < 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);
			//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

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:88:21: warning: variable 'id' set but not used [-Wunused-but-set-variable]
   88 |   int p = 0, r = 0, id = 0;
      |                     ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1740 KB Output is correct
2 Correct 11 ms 1776 KB Output is correct
3 Correct 12 ms 1704 KB Output is correct
4 Correct 12 ms 1688 KB Output is correct
5 Correct 14 ms 1716 KB Output is correct
6 Correct 27 ms 1780 KB Output is correct
7 Correct 50 ms 1716 KB Output is correct

Subtask #2
59.00003 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 877 ms 1720 KB Output is partially correct
2 Partially correct 311 ms 1668 KB Output is partially correct
3 Partially correct 546 ms 1664 KB Output is partially correct
4 Partially correct 809 ms 1664 KB Output is partially correct
5 Partially correct 636 ms 1660 KB Output is partially correct
6 Partially correct 643 ms 1732 KB Output is partially correct
7 Partially correct 2267 ms 1816 KB Output is partially correct
8 Partially correct 3453 ms 1876 KB Output is partially correct
9 Partially correct 3224 ms 1960 KB Output is partially correct
10 Partially correct 3293 ms 1820 KB Output is partially correct
11 Partially correct 3231 ms 1896 KB Output is partially correct
12 Partially correct 3234 ms 1816 KB Output is partially correct
13 Partially correct 3482 ms 1928 KB Output is partially correct
14 Partially correct 3004 ms 1788 KB Output is partially correct
15 Partially correct 1722 ms 1844 KB Output is partially correct
16 Partially correct 3909 ms 1732 KB Output is partially correct
17 Partially correct 1027 ms 1916 KB Output is partially correct
18 Partially correct 851 ms 1812 KB Output is partially correct
19 Partially correct 911 ms 1856 KB Output is partially correct
20 Partially correct 1146 ms 1732 KB Output is partially correct
21 Partially correct 888 ms 1732 KB Output is partially correct
22 Partially correct 897 ms 1780 KB Output is partially correct
23 Partially correct 1490 ms 1728 KB Output is partially correct
24 Correct 9 ms 1656 KB Output is correct
25 Correct 11 ms 1736 KB Output is correct
26 Correct 20 ms 1700 KB Output is correct
27 Correct 8 ms 1696 KB Output is correct
28 Correct 15 ms 1720 KB Output is correct
29 Correct 27 ms 1832 KB Output is correct
30 Correct 55 ms 1872 KB Output is correct