#include "communication.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
typedef pair<int,int> pii;
//we want a solution that returns a mask where either flipped or unflipped is correct
void get(vector<int>v){
if(v.size() <= 1)return;
vector<int>res,nxt;
int n = v.size();
for(int x:v){
res.pb(send(x));
res.pb(send(x));
}
for(int i=0;i<n;i++){
if(res[2*i] == res[2*i+1])continue;
int j = i;
while(j+1<n && res[2*j+2] != res[2*j+3])j++;
nxt.pb(res[2*i] != v[i]);
i=j;
}
//equal segment take the bit value of the left guy
get(nxt);
}
//cw = 1
//wc = 0
vector<int>solve(int n){
if(n<=1)return {0};
vector<int>res,nxt,ans(n,0);
for(int i=0;i<2*n;i++)res.pb(receive());
for(int i=0;i<n;i++){
if(res[2*i] == res[2*i+1])continue;
int j = i;
while(j+1<n && res[2*j+2] != res[2*j+3])j++;
nxt.pb(i/2);
i=j;
}
if(nxt.empty()){ //all equal
for(int i=0;i<2*n;i++)ans[i/2] = res[i];
return ans;
}
vector<int>sol = solve(nxt.size());
int ptr = 0;
for(int i=0;i<n;i++){
if(res[2*i] == res[2*i+1]){
if(ptr == (int)(sol.size()))ptr--;
ans[i] = res[2*i] ^ sol[ptr];
continue;
}
int j = i;
while(j+1<n && res[2*j+2] != res[2*j+3])j++;
for(int k=i;k<=j;k++)ans[k] = res[2*k] ^ sol[ptr];
ptr++;
i=j;
}
return ans;
}
void encode(int n, int x) {
vector<int>v;
int lim = 0;
for(int i=30;i>=0;i--){
if(n&(1<<i)){
lim = i;
break;
}
}
for(int i=0;i<=lim;i++)v.pb((x&(1<<i))>0);
get(v);
}
pair<int, int> decode(int n) {
pair<int,int>ans = {1,1};
int lim = 0;
for(int i=30;i>=0;i--){
if(n&(1<<i)){
lim = i;
break;
}
}
int a = 0;
int b = 0;
vector<int>v = solve(lim+1);
for(int i=0;i<=lim;i++){
if(v[i])a+=(1<<i);
else b+=(1<<i);
}
if(a>0 && a<=n)ans.fi = a;
if(b>0 && b<=n)ans.se = b;
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
212 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
292 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
