#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[128];
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<128;i++){
valid[i] = 1;
for (int j=0;j<6;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, 128, X, 7);
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<128;i++){
valid[i] = 1;
for (int j=0;j<6;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, 128, 0, 7);
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 |
9 ms |
1740 KB |
Output is correct |
| 2 |
Correct |
17 ms |
1768 KB |
Output is correct |
| 3 |
Correct |
18 ms |
1820 KB |
Output is correct |
| 4 |
Correct |
9 ms |
1680 KB |
Output is correct |
| 5 |
Correct |
15 ms |
1856 KB |
Output is correct |
| 6 |
Correct |
24 ms |
1852 KB |
Output is correct |
| 7 |
Correct |
41 ms |
1660 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
821 ms |
1828 KB |
Output is partially correct |
| 2 |
Partially correct |
771 ms |
1760 KB |
Output is partially correct |
| 3 |
Partially correct |
514 ms |
1748 KB |
Output is partially correct |
| 4 |
Partially correct |
970 ms |
1796 KB |
Output is partially correct |
| 5 |
Partially correct |
826 ms |
1836 KB |
Output is partially correct |
| 6 |
Partially correct |
617 ms |
1792 KB |
Output is partially correct |
| 7 |
Partially correct |
2698 ms |
2028 KB |
Output is partially correct |
| 8 |
Partially correct |
4153 ms |
2188 KB |
Output is partially correct |
| 9 |
Partially correct |
3244 ms |
2032 KB |
Output is partially correct |
| 10 |
Partially correct |
3655 ms |
2052 KB |
Output is partially correct |
| 11 |
Partially correct |
3643 ms |
2116 KB |
Output is partially correct |
| 12 |
Partially correct |
3526 ms |
1884 KB |
Output is partially correct |
| 13 |
Partially correct |
3624 ms |
2060 KB |
Output is partially correct |
| 14 |
Partially correct |
3560 ms |
2108 KB |
Output is partially correct |
| 15 |
Partially correct |
2016 ms |
1944 KB |
Output is partially correct |
| 16 |
Partially correct |
4057 ms |
1920 KB |
Output is partially correct |
| 17 |
Partially correct |
974 ms |
2092 KB |
Output is partially correct |
| 18 |
Partially correct |
1086 ms |
2024 KB |
Output is partially correct |
| 19 |
Partially correct |
1063 ms |
1832 KB |
Output is partially correct |
| 20 |
Partially correct |
1119 ms |
1960 KB |
Output is partially correct |
| 21 |
Partially correct |
1150 ms |
1928 KB |
Output is partially correct |
| 22 |
Partially correct |
1007 ms |
2084 KB |
Output is partially correct |
| 23 |
Partially correct |
1654 ms |
1876 KB |
Output is partially correct |
| 24 |
Correct |
15 ms |
1916 KB |
Output is correct |
| 25 |
Correct |
16 ms |
1928 KB |
Output is correct |
| 26 |
Correct |
18 ms |
1832 KB |
Output is correct |
| 27 |
Correct |
13 ms |
1700 KB |
Output is correct |
| 28 |
Correct |
14 ms |
1756 KB |
Output is correct |
| 29 |
Correct |
28 ms |
1848 KB |
Output is correct |
| 30 |
Correct |
45 ms |
1760 KB |
Output is correct |
