//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
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;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
1736 KB |
Output is correct |
| 2 |
Correct |
11 ms |
1656 KB |
Output is correct |
| 3 |
Correct |
17 ms |
1764 KB |
Output is correct |
| 4 |
Correct |
10 ms |
1780 KB |
Output is correct |
| 5 |
Correct |
11 ms |
1796 KB |
Output is correct |
| 6 |
Correct |
29 ms |
1916 KB |
Output is correct |
| 7 |
Correct |
40 ms |
1716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
420 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
