#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, 64, X, 6);
process(V, S, 32, X, 5);
process(V, S, 16, X, 4);
process(V, S, 8, X, 3);
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, 64, 0, 6);
process(V, S, 32, 0, 5);
process(V, S, 16, 0, 4);
process(V, S, 8, 0, 3);
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 |
1784 KB |
Output is correct |
| 2 |
Correct |
9 ms |
1704 KB |
Output is correct |
| 3 |
Correct |
16 ms |
1772 KB |
Output is correct |
| 4 |
Correct |
12 ms |
1888 KB |
Output is correct |
| 5 |
Correct |
14 ms |
1792 KB |
Output is correct |
| 6 |
Correct |
29 ms |
1752 KB |
Output is correct |
| 7 |
Correct |
37 ms |
1784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
839 ms |
1896 KB |
Output is partially correct |
| 2 |
Partially correct |
444 ms |
1824 KB |
Output is partially correct |
| 3 |
Partially correct |
595 ms |
1776 KB |
Output is partially correct |
| 4 |
Partially correct |
1080 ms |
1816 KB |
Output is partially correct |
| 5 |
Partially correct |
891 ms |
1744 KB |
Output is partially correct |
| 6 |
Partially correct |
604 ms |
1912 KB |
Output is partially correct |
| 7 |
Partially correct |
2582 ms |
1924 KB |
Output is partially correct |
| 8 |
Partially correct |
3966 ms |
2260 KB |
Output is partially correct |
| 9 |
Partially correct |
3791 ms |
2128 KB |
Output is partially correct |
| 10 |
Partially correct |
3730 ms |
2008 KB |
Output is partially correct |
| 11 |
Partially correct |
3658 ms |
2196 KB |
Output is partially correct |
| 12 |
Partially correct |
3799 ms |
2000 KB |
Output is partially correct |
| 13 |
Partially correct |
3889 ms |
2108 KB |
Output is partially correct |
| 14 |
Partially correct |
3774 ms |
2156 KB |
Output is partially correct |
| 15 |
Partially correct |
2096 ms |
2004 KB |
Output is partially correct |
| 16 |
Partially correct |
4463 ms |
1944 KB |
Output is partially correct |
| 17 |
Partially correct |
1101 ms |
1940 KB |
Output is partially correct |
| 18 |
Partially correct |
1113 ms |
1904 KB |
Output is partially correct |
| 19 |
Partially correct |
1052 ms |
2032 KB |
Output is partially correct |
| 20 |
Partially correct |
1186 ms |
2032 KB |
Output is partially correct |
| 21 |
Partially correct |
1055 ms |
1932 KB |
Output is partially correct |
| 22 |
Partially correct |
1043 ms |
1964 KB |
Output is partially correct |
| 23 |
Partially correct |
1899 ms |
2188 KB |
Output is partially correct |
| 24 |
Correct |
15 ms |
1864 KB |
Output is correct |
| 25 |
Correct |
15 ms |
1664 KB |
Output is correct |
| 26 |
Correct |
16 ms |
1764 KB |
Output is correct |
| 27 |
Correct |
10 ms |
1760 KB |
Output is correct |
| 28 |
Correct |
17 ms |
1672 KB |
Output is correct |
| 29 |
Correct |
25 ms |
1888 KB |
Output is correct |
| 30 |
Correct |
55 ms |
1780 KB |
Output is correct |
