#include "communication.h"
#include <bits/stdc++.h>
//
// --- 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
//
using namespace std;
typedef long long ll;
int valid[64];
int _find(const vector<pair<int, int>> &V, int S, int k, int X){
int cur = V[0].first;
int pt = 0;
int ret = 0;
int rem = S / k;
if (S%k) rem++;
while(true){
int r = min(cur+rem-1, V[pt].second);
if (X>=cur && X<=r) return ret;
S -= r-cur+1;
rem -= r-cur+1;
if (rem==0){
--k;
assert(k);
rem = S/k;
if (S%k) rem++;
ret++;
}
cur = r+1;
if (cur>V[pt].second){
++pt;
cur = V[pt].first;
}
}
assert(0);
}
void _modify(vector<pair<int, int>> &V, int &S, int k, int val){
vector<pair<int, int>> ret;
int retS = 0;
int cur = V[0].first;
int pt = 0, idx = 0;
int rem = S / k;
if (S%k) rem++;
while(true){
int r = min(cur+rem-1, V[pt].second);
if (valid[idx^val]){
//printf(" %d %d\n", idx, val);
ret.emplace_back(cur, r);
retS += r-cur+1;
}
S -= r-cur+1;
rem -= r-cur+1;
if (rem==0){
--k;
if (!k) break;
rem = S/k;
if (S%k) rem++;
idx++;
}
cur = r+1;
if (cur>V[pt].second){
++pt;
cur = V[pt].first;
}
}
swap(V, ret);
swap(S, retS);
}
vector<int> get_last(const vector<pair<int, int>> &V){
vector<int> ret;
for (auto &[l, r]:V){
for (int i=l;i<=r;i++) ret.push_back(i);
}
assert(ret.size()==3);
return ret;
}
void process(vector<pair<int, int>> &V, int &S, int k, int encode, int t){
while(S>=k){
int val = 0;
if (encode) val = _find(V, S, k, encode);
int rval = 0;
if (encode){
for (int i=0;i<t;i++){
if (val&(1<<i)) rval |= (send(1)<<i);
else rval |= (send(0)<<i);
}
}
else{
for (int i=0;i<t;i++){
rval |= (receive()<<i);
}
}
_modify(V, S, k, rval);
//for (auto &[l, r]:V) printf("[%d, %d] ", l, r);
//printf("-> %d\n", S);
}
}
void encode(int N, int X) {
for (int i=0;i<64;i++){
valid[i] = 1;
for (int j=0;j<5;j++) if ((i&(1<<j)) && (i&(1<<(j+1)))) valid[i] = 0;
}
vector<pair<int, int>> V = {{1, N}};
int S = N;
process(V, S, 16, X, 4);
process(V, S, 4, X, 2);
vector<int> last = get_last(V);
X = find(last.begin(), last.end(), X) - last.begin() + 1;
assert(X<=3);
string s[4] = {"", "10", "11", "01"};
bool flag = 0;
for (int i=0;i<3;i++){
if (!flag) flag = (((s[X][0]-'0')^1) != send((s[X][0]-'0') ^ 1));
else{
send(s[X][1]-'0');
flag = 0;
}
}
}
std::pair<int, int> decode(int N) {
for (int i=0;i<64;i++){
valid[i] = 1;
for (int j=0;j<5;j++) if ((i&(1<<j)) && (i&(1<<(j+1)))) valid[i] = 0;
}
vector<pair<int, int>> V = {{1, N}};
int S = N;
process(V, S, 16, 0, 4);
process(V, S, 4, 0, 2);
vector<int> last = get_last(V);
vector<int> v;
for (int i=0;i<3;i++){
int x = receive();
v.push_back(x);
if (i && v[i-1]==v[i]){
if (v[i]==1) return {last[1], last[2]};
else return {last[0], last[1]};
}
}
return {last[0], last[2]};
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
1960 KB |
Output is correct |
| 2 |
Correct |
11 ms |
1688 KB |
Output is correct |
| 3 |
Correct |
18 ms |
1844 KB |
Output is correct |
| 4 |
Correct |
11 ms |
1892 KB |
Output is correct |
| 5 |
Correct |
15 ms |
1860 KB |
Output is correct |
| 6 |
Correct |
24 ms |
1728 KB |
Output is correct |
| 7 |
Correct |
31 ms |
1872 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
939 ms |
1800 KB |
Output is partially correct |
| 2 |
Partially correct |
448 ms |
1772 KB |
Output is partially correct |
| 3 |
Partially correct |
560 ms |
1676 KB |
Output is partially correct |
| 4 |
Partially correct |
817 ms |
1832 KB |
Output is partially correct |
| 5 |
Partially correct |
1029 ms |
1808 KB |
Output is partially correct |
| 6 |
Partially correct |
827 ms |
1720 KB |
Output is partially correct |
| 7 |
Partially correct |
2585 ms |
1968 KB |
Output is partially correct |
| 8 |
Partially correct |
4572 ms |
2044 KB |
Output is partially correct |
| 9 |
Partially correct |
3840 ms |
1916 KB |
Output is partially correct |
| 10 |
Partially correct |
3885 ms |
1968 KB |
Output is partially correct |
| 11 |
Partially correct |
3856 ms |
1816 KB |
Output is partially correct |
| 12 |
Partially correct |
3858 ms |
2020 KB |
Output is partially correct |
| 13 |
Partially correct |
3826 ms |
1804 KB |
Output is partially correct |
| 14 |
Partially correct |
4037 ms |
2092 KB |
Output is partially correct |
| 15 |
Partially correct |
2066 ms |
1984 KB |
Output is partially correct |
| 16 |
Partially correct |
4269 ms |
1928 KB |
Output is partially correct |
| 17 |
Partially correct |
888 ms |
1828 KB |
Output is partially correct |
| 18 |
Partially correct |
1029 ms |
1916 KB |
Output is partially correct |
| 19 |
Partially correct |
1080 ms |
1824 KB |
Output is partially correct |
| 20 |
Partially correct |
1099 ms |
1828 KB |
Output is partially correct |
| 21 |
Partially correct |
1194 ms |
1872 KB |
Output is partially correct |
| 22 |
Partially correct |
1132 ms |
1764 KB |
Output is partially correct |
| 23 |
Partially correct |
1912 ms |
1892 KB |
Output is partially correct |
| 24 |
Correct |
12 ms |
1792 KB |
Output is correct |
| 25 |
Correct |
12 ms |
1852 KB |
Output is correct |
| 26 |
Correct |
21 ms |
1764 KB |
Output is correct |
| 27 |
Correct |
12 ms |
1812 KB |
Output is correct |
| 28 |
Correct |
10 ms |
1740 KB |
Output is correct |
| 29 |
Correct |
30 ms |
1784 KB |
Output is correct |
| 30 |
Correct |
52 ms |
1820 KB |
Output is correct |
