#include <bits/stdc++.h>
#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 = 1, l = -1, last = -1;
while (todo.size() > 1) {
int b1 = *todo.begin(), b2 = *++todo.begin();
vector<int> res(4);
if (b1 == last) res[0] = l;
else res[0] = send((x >> b1) & 1);
res[1] = send((x >> b2) & 1);
res[2] = send((x >> b2) & 1);
if (res[1] == res[2]) {
a |= res[1] << b2, b |= res[1] << b2;
todo.erase(b2);
l = res[2], last = b2;
continue;
}
res[3] = send((x >> b1) & 1);
l = res[3], last = b1;
if (res[0] == res[3]) {
s(a, b1, res[0]), s(b, b1, res[0]), s(b, b2, 1);
int taken = 0;
for (int i = 0; i < same.size() - taken; ++i)
if (same[i].first == b1)
swap(same[i], same[same.size() - 1 - taken++]), --i;
for (int i = 0; i < taken; ++i) {
s(a, same[same.size() - 1 - i].second, (a >> b1) & 1);
s(b, same[same.size() - 1 - i].second, (b >> b1) & 1);
}
same.resize(same.size() - taken);
taken = 0;
for (int i = 0; i < diff.size() - taken; ++i)
if (diff[i].first == b1)
swap(diff[i], diff[diff.size() - 1 - taken++]), --i;
for (int i = 0; i < taken; ++i) {
s(a, diff[diff.size() - 1 - i].second, 1 - ((a >> b1) & 1));
s(b, diff[diff.size() - 1 - i].second, 1 - ((b >> b1) & 1));
}
diff.resize(diff.size() - taken);
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(b2);
}
}
}
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 = 1, l = -1, last = -1;
while (todo.size() > 1) {
int b1 = *todo.begin(), b2 = *++todo.begin();
vector<int> res(4);
if (b1 == last) res[0] = l;
else res[0] = receive();
res[1] = receive();
res[2] = receive();
if (res[1] == res[2]) {
a |= res[1] << b2, b |= res[1] << b2;
todo.erase(b2);
l = res[2], last = b2;
continue;
}
res[3] = receive();
l = res[3], last = b1;
if (res[0] == res[3]) {
s(a, b1, res[0]), s(b, b1, res[0]), s(b, b2, 1);
int taken = 0;
for (int i = 0; i < same.size() - taken; ++i)
if (same[i].first == b1)
swap(same[i], same[same.size() - 1 - taken++]), --i;
for (int i = 0; i < taken; ++i) {
s(a, same[same.size() - 1 - i].second, (a >> b1) & 1);
s(b, same[same.size() - 1 - i].second, (b >> b1) & 1);
}
same.resize(same.size() - taken);
taken = 0;
for (int i = 0; i < diff.size() - taken; ++i)
if (diff[i].first == b1)
swap(diff[i], diff[diff.size() - 1 - taken++]), --i;
for (int i = 0; i < taken; ++i) {
s(a, diff[diff.size() - 1 - i].second, 1 - ((a >> b1) & 1));
s(b, diff[diff.size() - 1 - i].second, 1 - ((b >> b1) & 1));
}
diff.resize(diff.size() - taken);
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(b2);
}
}
return {max(min(a, n), 1), max(min(b, n), 1)};
}
Compilation message
communication.cpp: In function 'void encode(int, int)':
communication.cpp:29:25: 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() - taken; ++i)
| ~~^~~~~~~~~~~~~~~~~~~~~
communication.cpp:38:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for (int i = 0; i < diff.size() - taken; ++i)
| ~~^~~~~~~~~~~~~~~~~~~~~
communication.cpp: In function 'std::pair<int, int> decode(int)':
communication.cpp:82:25: 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 < same.size() - taken; ++i)
| ~~^~~~~~~~~~~~~~~~~~~~~
communication.cpp:91:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for (int i = 0; i < diff.size() - taken; ++i)
| ~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
1680 KB |
Output is correct |
| 2 |
Correct |
141 ms |
1848 KB |
Output is correct |
| 3 |
Correct |
175 ms |
1780 KB |
Output is correct |
| 4 |
Correct |
69 ms |
1704 KB |
Output is correct |
| 5 |
Correct |
118 ms |
1720 KB |
Output is correct |
| 6 |
Correct |
276 ms |
1808 KB |
Output is correct |
| 7 |
Correct |
521 ms |
1672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
821 ms |
1664 KB |
Output is partially correct |
| 2 |
Partially correct |
378 ms |
1784 KB |
Output is partially correct |
| 3 |
Partially correct |
468 ms |
1872 KB |
Output is partially correct |
| 4 |
Partially correct |
613 ms |
1776 KB |
Output is partially correct |
| 5 |
Partially correct |
632 ms |
1848 KB |
Output is partially correct |
| 6 |
Correct |
425 ms |
1740 KB |
Output is correct |
| 7 |
Correct |
2055 ms |
1764 KB |
Output is correct |
| 8 |
Correct |
2778 ms |
1944 KB |
Output is correct |
| 9 |
Correct |
2437 ms |
2080 KB |
Output is correct |
| 10 |
Correct |
2548 ms |
1968 KB |
Output is correct |
| 11 |
Correct |
2369 ms |
2060 KB |
Output is correct |
| 12 |
Correct |
2521 ms |
1876 KB |
Output is correct |
| 13 |
Correct |
2377 ms |
2092 KB |
Output is correct |
| 14 |
Correct |
2441 ms |
1920 KB |
Output is correct |
| 15 |
Correct |
1257 ms |
1876 KB |
Output is correct |
| 16 |
Correct |
2699 ms |
1748 KB |
Output is correct |
| 17 |
Correct |
750 ms |
1724 KB |
Output is correct |
| 18 |
Correct |
628 ms |
2024 KB |
Output is correct |
| 19 |
Correct |
573 ms |
1788 KB |
Output is correct |
| 20 |
Correct |
692 ms |
1740 KB |
Output is correct |
| 21 |
Correct |
723 ms |
1880 KB |
Output is correct |
| 22 |
Correct |
715 ms |
1880 KB |
Output is correct |
| 23 |
Correct |
1041 ms |
1844 KB |
Output is correct |
| 24 |
Correct |
100 ms |
1732 KB |
Output is correct |
| 25 |
Correct |
107 ms |
1876 KB |
Output is correct |
| 26 |
Correct |
159 ms |
1732 KB |
Output is correct |
| 27 |
Correct |
79 ms |
1700 KB |
Output is correct |
| 28 |
Correct |
99 ms |
1880 KB |
Output is correct |
| 29 |
Correct |
325 ms |
1800 KB |
Output is correct |
| 30 |
Correct |
467 ms |
1700 KB |
Output is correct |
