//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 b) {
int len = (getlen(t) + b) / 2;
int cur = 0;
vector<vector<pii> > ret;
vector<pii> v;
bool fi = 0;
for (int i = 0;i < t.size();i++) {
pii p = t[i];
if (fi) {
v.push_back(p);
continue;
}
//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);
fi = 1;
cur = 0;
v.clear();
}
} else {
v.push_back({p.ff, p.ff + len - cur - 1});
t[i].ff += len - cur;
i--;
cur = 0;
fi = 1;
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) {
for (auto p:A) debug(p.ff, p.ss);
debug();
for (auto p:B) debug(p.ff, p.ss);
vector<vector<pii> > sa = split(A, 0), sb = split(B, 1);
int ask = 0;
if (in(X, sb[1]) || in(X, sa[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, 0), sb = split(B, 1);
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
communication.cpp: In function 'std::vector<std::vector<std::pair<int, int> > > split(std::vector<std::pair<int, 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 'std::vector<std::pair<int, int> > merge(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&)':
communication.cpp:82: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]
82 | for (int i = 0;i < s.size();i++) {
| ~~^~~~~~~~~~
communication.cpp:83: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]
83 | while (ind < t.size() && t[ind].ff < s[i].ff) ret.push_back(t[ind++]);
| ~~~~^~~~~~~~~~
communication.cpp:86: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]
86 | while (ind < t.size()) ret.push_back(t[ind++]);
| ~~~~^~~~~~~~~~
communication.cpp: In function 'void encode(int, int)':
communication.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 0
| ^
communication.cpp:104:18: note: in expansion of macro 'debug'
104 | for (auto p:A) debug(p.ff, p.ss);
| ^~~~~
communication.cpp:104:13: warning: variable 'p' set but not used [-Wunused-but-set-variable]
104 | for (auto p:A) debug(p.ff, p.ss);
| ^
communication.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 0
| ^
communication.cpp:105:3: note: in expansion of macro 'debug'
105 | debug();
| ^~~~~
communication.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 0
| ^
communication.cpp:106:18: note: in expansion of macro 'debug'
106 | for (auto p:B) debug(p.ff, p.ss);
| ^~~~~
communication.cpp:106:13: warning: variable 'p' set but not used [-Wunused-but-set-variable]
106 | for (auto p:B) debug(p.ff, p.ss);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1688 KB |
Output is correct |
| 2 |
Correct |
7 ms |
1680 KB |
Output is correct |
| 3 |
Correct |
14 ms |
1772 KB |
Output is correct |
| 4 |
Correct |
12 ms |
1640 KB |
Output is correct |
| 5 |
Correct |
17 ms |
1732 KB |
Output is correct |
| 6 |
Correct |
30 ms |
1784 KB |
Output is correct |
| 7 |
Correct |
46 ms |
1660 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
781 ms |
1716 KB |
Output is correct |
| 2 |
Correct |
309 ms |
1792 KB |
Output is correct |
| 3 |
Correct |
301 ms |
1756 KB |
Output is correct |
| 4 |
Correct |
883 ms |
1740 KB |
Output is correct |
| 5 |
Correct |
554 ms |
1728 KB |
Output is correct |
| 6 |
Correct |
601 ms |
1736 KB |
Output is correct |
| 7 |
Correct |
2025 ms |
1832 KB |
Output is correct |
| 8 |
Correct |
3528 ms |
2072 KB |
Output is correct |
| 9 |
Correct |
2779 ms |
1920 KB |
Output is correct |
| 10 |
Correct |
2924 ms |
1800 KB |
Output is correct |
| 11 |
Correct |
2752 ms |
1964 KB |
Output is correct |
| 12 |
Correct |
2727 ms |
1916 KB |
Output is correct |
| 13 |
Correct |
2963 ms |
1936 KB |
Output is correct |
| 14 |
Correct |
3085 ms |
1924 KB |
Output is correct |
| 15 |
Correct |
1600 ms |
1872 KB |
Output is correct |
| 16 |
Correct |
3246 ms |
1736 KB |
Output is correct |
| 17 |
Correct |
888 ms |
1828 KB |
Output is correct |
| 18 |
Correct |
791 ms |
1748 KB |
Output is correct |
| 19 |
Correct |
877 ms |
1760 KB |
Output is correct |
| 20 |
Correct |
925 ms |
1728 KB |
Output is correct |
| 21 |
Correct |
767 ms |
1808 KB |
Output is correct |
| 22 |
Correct |
875 ms |
1728 KB |
Output is correct |
| 23 |
Correct |
1393 ms |
1832 KB |
Output is correct |
| 24 |
Correct |
5 ms |
1708 KB |
Output is correct |
| 25 |
Correct |
9 ms |
1752 KB |
Output is correct |
| 26 |
Correct |
15 ms |
1684 KB |
Output is correct |
| 27 |
Correct |
11 ms |
1708 KB |
Output is correct |
| 28 |
Correct |
10 ms |
1684 KB |
Output is correct |
| 29 |
Correct |
23 ms |
1856 KB |
Output is correct |
| 30 |
Correct |
53 ms |
1708 KB |
Output is correct |
