#include <vector>
#include <set>
#include <iostream>
#include "communication.h"
using namespace std;
inline void s(int& x, int b, int v) { x -= (x & (1 << b)), x |= v << b; }
void encode(int n, int x) {
set<int> todo; for (int i = 0; i < 30; ++i) todo.insert(i);
vector<pair<int, int>> same, diff;
int a = 0, b = 0; b |= 1;
while (todo.size() > 1) {
int b1 = *todo.begin(), b2 = *++todo.begin();
vector<int> res(4);
res[0] = send((x >> b1) & 1);
res[1] = send((x >> b2) & 1);
res[2] = send((x >> b2) & 1);
res[3] = send((x >> b1) & 1);
if (res[1] == res[2]) {
a |= res[1] << b2, b |= res[1] << b2;
todo.erase(b2);
} else if (res[0] == res[3]) {
s(a, b1, res[0]), s(b, b1, res[0]), s(b, b2, 1);
int cur = b1;
while (same.size() || diff.size()) {
pair<int, int> l;
if (same.size()) {
for (int i = 0; i < same.size(); ++i) {
if (same[i].second == cur) {
swap(same[i], same[same.size() - 1]);
break;
}
}
l = same.back();
if (l.second == cur) {
s(a, l.first, (a >> cur) & 1);
s(b, l.first, (b >> cur) & 1);
cur = l.first;
same.resize(same.size() - 1);
continue;
}
}
if (!diff.size()) break;
for (int i = 0; i < diff.size(); ++i) {
if (diff[i].second == cur) {
swap(diff[i], diff[diff.size() - 1]);
break;
}
}
l = diff.back();
if (l.second != cur) break;
s(a, l.first, 1 - ((a >> cur) & 1));
s(b, l.first, 1 - ((b >> cur) & 1));
cur = l.first;
diff.resize(diff.size() - 1);
}
todo.erase(b1);
} else {
int pa = (res[0] == res[1]), pb = 3 - pa;
if (pa) diff.push_back({b1, b2});
else same.push_back({b1, b2});
if (a & (1 << b1)) a |= (pb & 1) << b2;
else a |= (pa & 1) << b2;
if (b & (1 << b1)) b |= (pb & 1) << b2;
else b |= (pa & 1) << b2;
todo.erase(b1);
}
}
}
pair<int, int> decode(int n) {
set<int> todo; for (int i = 0; i < 30; ++i) todo.insert(i);
vector<pair<int, int>> same, diff;
int a = 0, b = 0; b |= 1;
while (todo.size() > 1) {
int b1 = *todo.begin(), b2 = *++todo.begin();
vector<int> res(4);
for (int i = 0; i < 4; ++i) res[i] = receive();
if (res[1] == res[2]) {
a |= res[1] << b2, b |= res[1] << b2;
todo.erase(b2);
} else if (res[0] == res[3]) {
s(a, b1, res[0]), s(b, b1, res[0]), s(b, b2, 1);
int cur = b1;
while (same.size() || diff.size()) {
pair<int, int> l;
if (same.size()) {
for (int i = 0; i < same.size(); ++i) {
if (same[i].second == cur) {
swap(same[i], same[same.size() - 1]);
break;
}
}
l = same.back();
if (l.second == cur) {
s(a, l.first, (a >> cur) & 1);
s(b, l.first, (b >> cur) & 1);
cur = l.first;
same.resize(same.size() - 1);
continue;
}
}
if (!diff.size()) break;
for (int i = 0; i < diff.size(); ++i) {
if (diff[i].second == cur) {
swap(diff[i], diff[diff.size() - 1]);
break;
}
}
l = diff.back();
if (l.second != cur) break;
s(a, l.first, 1 - ((a >> cur) & 1));
s(b, l.first, 1 - ((b >> cur) & 1));
cur = l.first;
diff.resize(diff.size() - 1);
}
todo.erase(b1);
} else {
int pa = (res[0] == res[1]), pb = 3 - pa;
if (pa) diff.push_back({b1, b2});
else same.push_back({b1, b2});
if (a & (1 << b1)) a |= (pb & 1) << b2;
else a |= (pa & 1) << b2;
if (b & (1 << b1)) b |= (pb & 1) << b2;
else b |= (pa & 1) << b2;
todo.erase(b1);
}
}
return {max(min(a, n), 1), max(min(b, n), 1)};
}
Compilation message
communication.cpp: In function 'void encode(int, int)':
communication.cpp:29:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for (int i = 0; i < same.size(); ++i) {
| ~~^~~~~~~~~~~~~
communication.cpp:45:27: 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 < diff.size(); ++i) {
| ~~^~~~~~~~~~~~~
communication.cpp: In function 'std::pair<int, int> decode(int)':
communication.cpp:89:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for (int i = 0; i < same.size(); ++i) {
| ~~^~~~~~~~~~~~~
communication.cpp:105:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for (int i = 0; i < diff.size(); ++i) {
| ~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
111 ms |
1736 KB |
Output is correct |
2 |
Correct |
120 ms |
1668 KB |
Output is correct |
3 |
Correct |
218 ms |
1744 KB |
Output is correct |
4 |
Correct |
100 ms |
1832 KB |
Output is correct |
5 |
Correct |
167 ms |
1752 KB |
Output is correct |
6 |
Correct |
375 ms |
1856 KB |
Output is correct |
7 |
Correct |
673 ms |
1948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
903 ms |
1692 KB |
Output is partially correct |
2 |
Partially correct |
410 ms |
1724 KB |
Output is partially correct |
3 |
Partially correct |
460 ms |
1756 KB |
Output is partially correct |
4 |
Partially correct |
935 ms |
1700 KB |
Output is partially correct |
5 |
Partially correct |
809 ms |
1708 KB |
Output is partially correct |
6 |
Partially correct |
554 ms |
1772 KB |
Output is partially correct |
7 |
Partially correct |
2231 ms |
1912 KB |
Output is partially correct |
8 |
Partially correct |
3894 ms |
2044 KB |
Output is partially correct |
9 |
Partially correct |
3216 ms |
2040 KB |
Output is partially correct |
10 |
Partially correct |
3126 ms |
1952 KB |
Output is partially correct |
11 |
Partially correct |
3203 ms |
2052 KB |
Output is partially correct |
12 |
Partially correct |
3034 ms |
1984 KB |
Output is partially correct |
13 |
Partially correct |
2879 ms |
2048 KB |
Output is partially correct |
14 |
Partially correct |
2985 ms |
1912 KB |
Output is partially correct |
15 |
Partially correct |
1445 ms |
1724 KB |
Output is partially correct |
16 |
Partially correct |
3717 ms |
1808 KB |
Output is partially correct |
17 |
Partially correct |
1001 ms |
1880 KB |
Output is partially correct |
18 |
Partially correct |
890 ms |
1864 KB |
Output is partially correct |
19 |
Partially correct |
822 ms |
1836 KB |
Output is partially correct |
20 |
Partially correct |
959 ms |
1816 KB |
Output is partially correct |
21 |
Partially correct |
845 ms |
1804 KB |
Output is partially correct |
22 |
Partially correct |
701 ms |
1828 KB |
Output is partially correct |
23 |
Partially correct |
1468 ms |
1828 KB |
Output is partially correct |
24 |
Correct |
116 ms |
1708 KB |
Output is correct |
25 |
Correct |
152 ms |
1688 KB |
Output is correct |
26 |
Correct |
262 ms |
1660 KB |
Output is correct |
27 |
Correct |
96 ms |
1756 KB |
Output is correct |
28 |
Correct |
117 ms |
1660 KB |
Output is correct |
29 |
Correct |
299 ms |
1740 KB |
Output is correct |
30 |
Correct |
667 ms |
1672 KB |
Output is correct |