#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, 64, X, 6);
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, 64, 0, 6);
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 |
10 ms |
1788 KB |
Output is correct |
| 2 |
Correct |
19 ms |
1888 KB |
Output is correct |
| 3 |
Correct |
17 ms |
1832 KB |
Output is correct |
| 4 |
Correct |
11 ms |
1852 KB |
Output is correct |
| 5 |
Correct |
14 ms |
1756 KB |
Output is correct |
| 6 |
Correct |
26 ms |
1808 KB |
Output is correct |
| 7 |
Correct |
54 ms |
1860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
799 ms |
2100 KB |
Output is partially correct |
| 2 |
Partially correct |
454 ms |
1820 KB |
Output is partially correct |
| 3 |
Partially correct |
684 ms |
1888 KB |
Output is partially correct |
| 4 |
Partially correct |
897 ms |
1752 KB |
Output is partially correct |
| 5 |
Partially correct |
803 ms |
1820 KB |
Output is partially correct |
| 6 |
Partially correct |
743 ms |
1832 KB |
Output is partially correct |
| 7 |
Partially correct |
2510 ms |
2064 KB |
Output is partially correct |
| 8 |
Partially correct |
4240 ms |
2256 KB |
Output is partially correct |
| 9 |
Partially correct |
3717 ms |
1972 KB |
Output is partially correct |
| 10 |
Partially correct |
3481 ms |
2172 KB |
Output is partially correct |
| 11 |
Partially correct |
3592 ms |
2148 KB |
Output is partially correct |
| 12 |
Partially correct |
3678 ms |
2176 KB |
Output is partially correct |
| 13 |
Partially correct |
3653 ms |
2148 KB |
Output is partially correct |
| 14 |
Partially correct |
3533 ms |
2172 KB |
Output is partially correct |
| 15 |
Partially correct |
2128 ms |
1940 KB |
Output is partially correct |
| 16 |
Partially correct |
4104 ms |
1964 KB |
Output is partially correct |
| 17 |
Partially correct |
1061 ms |
2052 KB |
Output is partially correct |
| 18 |
Partially correct |
1091 ms |
2068 KB |
Output is partially correct |
| 19 |
Partially correct |
1137 ms |
2216 KB |
Output is partially correct |
| 20 |
Partially correct |
976 ms |
1932 KB |
Output is partially correct |
| 21 |
Partially correct |
1239 ms |
1980 KB |
Output is partially correct |
| 22 |
Partially correct |
982 ms |
2012 KB |
Output is partially correct |
| 23 |
Partially correct |
1824 ms |
1956 KB |
Output is partially correct |
| 24 |
Correct |
11 ms |
1804 KB |
Output is correct |
| 25 |
Correct |
15 ms |
1808 KB |
Output is correct |
| 26 |
Correct |
13 ms |
1796 KB |
Output is correct |
| 27 |
Correct |
13 ms |
1852 KB |
Output is correct |
| 28 |
Correct |
15 ms |
1920 KB |
Output is correct |
| 29 |
Correct |
30 ms |
1912 KB |
Output is correct |
| 30 |
Correct |
52 ms |
1904 KB |
Output is correct |
