#include"communication.h"
#include <bits/stdc++.h>
using namespace std;
//
// --- Sample implementation for the task communication ---
//
// To compile this program with the sample grader, place:
// communication.h communication_sample.cpp sample_grader.cpp
// in a single folder, then open the terminal in this directory (right-click onto an empty spot in the directory,
// left click on "Open in terminal") and enter e.g.:
// g++ -std=c++17 communication_sample.cpp sample_grader.cpp
// in this folder. This will create a file a.out in the current directory which you can execute from the terminal
// as ./a.out
// See task statement or sample_grader.cpp for the input specification
//
void encode(int N, int X) {
int B = __lg(N + 1) + 1;
vector<int> bits; for(int j = 0; j < B; j++) bits.push_back(j);
vector<int> a; for(int j = 0; j < B; j++) a.push_back((X & (1 << j)) > 0);
while(bits.size() >= 2){
int b1 = bits.back(); bits.pop_back();
int b2 = bits.back(); bits.pop_back();
int s1 = send(a[b1]);
int s2 = send(a[b2]);
int s3 = send(a[b1]);
if(s1 == s3){
int s4 = send(a[b1]);
if(s3 == s4){
bits.push_back(b2);
continue;
}else{
int s5 = send(a[b2]);
bits.push_back(b1);
continue;
}
}else{
int s4 = send(a[b2]);
bits.push_back(b1);
}
}
}
struct DSU{
int dsu[71];
void init(){
for(int i = 0; i < 71; i++) dsu[i] = i;
}
int f(int x){ return x == dsu[x] ? x : dsu[x] = f(dsu[x]); }
void g(int x, int y){ x = f(x), y = f(y); dsu[x] = y; }
} dsu;
void link(int u, int v, bool b){
dsu.g(u * 2, v * 2 + b);
dsu.g(u * 2 + 1, v * 2 + !b);
}
std::pair<int, int> decode(int N) {
int B = __lg(N + 1) + 1;
vector<int> bits; for(int j = 0; j < B; j++) bits.push_back(j);
vector<int> a;
dsu.init();
while(bits.size() >= 2){
int b1 = bits.back(); bits.pop_back();
int b2 = bits.back(); bits.pop_back();
int s1 = receive();
int s2 = receive();
int s3 = receive();
if(s1 == s3){
int s4 = receive();
if(s3 == s4){
link(b1, B, s4);
bits.push_back(b2);
continue;
}else{
int s5 = receive();
if(s2 == s5){
link(b2, B, s5);
}else{
link(b1, b2, s1 ^ s2 ^ 1);
}
bits.push_back(b1);
continue;
}
}else{
int s4 = receive();
if(s2 == s4){
link(b2, B, s4);
}else{
link(b1, b2, s1 ^ s2 ^ 1);
}
bits.push_back(b1);
}
}
int sp = bits[0];
vector<int> ans;
for(int i = 0; i < 2; i++){
int r = 0;
for(int j = 0; j < B; j++){
bool y = dsu.f(j * 2) == dsu.f(B * 2 + 1) || dsu.f(j * 2) == dsu.f(sp * 2 + (1 - i));
r += (1 << j) * y;
}
ans.push_back(r);
}
if(ans[0] < 1 || ans[0] > N) ans[0] = 1;
if(ans[1] < 1 || ans[1] > N) ans[1] = 1;
return {ans[0], ans[1]};
}
Compilation message
communication.cpp: In function 'void encode(int, int)':
communication.cpp:35:21: warning: unused variable 's5' [-Wunused-variable]
35 | int s5 = send(a[b2]);
| ^~
communication.cpp:40:17: warning: unused variable 's4' [-Wunused-variable]
40 | int s4 = send(a[b2]);
| ^~
communication.cpp:27:13: warning: unused variable 's2' [-Wunused-variable]
27 | int s2 = send(a[b2]);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1684 KB |
Output is correct |
| 2 |
Correct |
13 ms |
1728 KB |
Output is correct |
| 3 |
Correct |
20 ms |
1668 KB |
Output is correct |
| 4 |
Correct |
11 ms |
1736 KB |
Output is correct |
| 5 |
Correct |
11 ms |
1736 KB |
Output is correct |
| 6 |
Correct |
34 ms |
1784 KB |
Output is correct |
| 7 |
Correct |
54 ms |
1680 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
629 ms |
1688 KB |
Output is partially correct |
| 2 |
Partially correct |
325 ms |
1700 KB |
Output is partially correct |
| 3 |
Partially correct |
440 ms |
1664 KB |
Output is partially correct |
| 4 |
Partially correct |
718 ms |
1684 KB |
Output is partially correct |
| 5 |
Partially correct |
720 ms |
1704 KB |
Output is partially correct |
| 6 |
Partially correct |
546 ms |
1744 KB |
Output is partially correct |
| 7 |
Partially correct |
2340 ms |
1788 KB |
Output is partially correct |
| 8 |
Partially correct |
3258 ms |
2036 KB |
Output is partially correct |
| 9 |
Partially correct |
2819 ms |
1928 KB |
Output is partially correct |
| 10 |
Partially correct |
2937 ms |
1824 KB |
Output is partially correct |
| 11 |
Partially correct |
2845 ms |
1952 KB |
Output is partially correct |
| 12 |
Partially correct |
2877 ms |
1876 KB |
Output is partially correct |
| 13 |
Partially correct |
3033 ms |
1944 KB |
Output is partially correct |
| 14 |
Partially correct |
2555 ms |
1820 KB |
Output is partially correct |
| 15 |
Partially correct |
1460 ms |
1872 KB |
Output is partially correct |
| 16 |
Partially correct |
3187 ms |
1856 KB |
Output is partially correct |
| 17 |
Partially correct |
812 ms |
1876 KB |
Output is partially correct |
| 18 |
Partially correct |
804 ms |
1724 KB |
Output is partially correct |
| 19 |
Partially correct |
956 ms |
1800 KB |
Output is partially correct |
| 20 |
Partially correct |
771 ms |
1820 KB |
Output is partially correct |
| 21 |
Partially correct |
859 ms |
1752 KB |
Output is partially correct |
| 22 |
Partially correct |
850 ms |
1752 KB |
Output is partially correct |
| 23 |
Partially correct |
1331 ms |
1820 KB |
Output is partially correct |
| 24 |
Correct |
9 ms |
1684 KB |
Output is correct |
| 25 |
Correct |
12 ms |
1692 KB |
Output is correct |
| 26 |
Correct |
20 ms |
1708 KB |
Output is correct |
| 27 |
Correct |
8 ms |
1680 KB |
Output is correct |
| 28 |
Correct |
10 ms |
1796 KB |
Output is correct |
| 29 |
Correct |
28 ms |
1848 KB |
Output is correct |
| 30 |
Correct |
62 ms |
1656 KB |
Output is correct |
