//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 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) + 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;
}
int st = 1;
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();
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 = s[id];
for (int i = 0;i < 4;i++) {
if (i != id && ((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:43: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]
43 | for (int i = 0;i < t.size();i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
1656 KB |
Output is correct |
| 2 |
Correct |
16 ms |
1684 KB |
Output is correct |
| 3 |
Correct |
15 ms |
1780 KB |
Output is correct |
| 4 |
Correct |
8 ms |
1600 KB |
Output is correct |
| 5 |
Correct |
10 ms |
1720 KB |
Output is correct |
| 6 |
Correct |
28 ms |
1816 KB |
Output is correct |
| 7 |
Correct |
49 ms |
1704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
292 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
