#include"communication.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for (int i=0; i<n; ++i)
pair<int,int> decode(int n) {
int len=4;
vector<vector<vector<vector<int>>>> dp((1<<len),vector<vector<vector<int>>>(len,vector<vector<int>>(2)));
for (int x=0; x<(1<<len); ++x) {
dp[x][0][0].push_back(x&1);
dp[x][0][1].push_back(!(x&1));
for (int l=1; l<len; ++l) {
for (auto v:dp[x][l-1][0]) {
dp[x][l][0].push_back(v+(x&(1<<l)));
dp[x][l][1].push_back(v+((!((x>>l)&1))<<l));
}
for (auto v:dp[x][l-1][1]) {
dp[x][l][0].push_back(v+(x&(1<<l)));
}
}
}
if (n==3) {
vector<int> paiu={1,2,3};
int x=0;
forn(i,4) {
int f=receive();
x<<=1;
x+=f;
}
vector<int> ans;
for (auto v:dp[0][len-1][0]) if (v==x) ans.push_back(paiu[0]);
for (auto v:dp[0][len-1][1]) if (v==x) ans.push_back(paiu[0]);
for (auto v:dp[6][len-1][0]) if (v==x) ans.push_back(paiu[1]);
for (auto v:dp[6][len-1][1]) if (v==x) ans.push_back(paiu[1]);
for (auto v:dp[9][len-1][0]) if (v==x) ans.push_back(paiu[2]);
for (auto v:dp[9][len-1][1]) if (v==x) ans.push_back(paiu[2]);
if (ans.size()==1) ans.push_back(ans[0]);
for (auto &x:ans) x=min(x,n);
return {ans[0],ans[1]};
}
int sq=sqrt(n)+1;
int first=0;
int second=0;
int a[40000], b[40000], a_sz=sq, b_sz=0;
for (int i=0; i<sq; ++i) a[i]=i;
while (a_sz>3) {
int n=a_sz;
int f=n/4+min(n%4,1);
int s=2*(n/4)+min(n%4,2);
int t=3*(n/4)+n%4;
int A=!receive(),B=!receive();
int y=(A<<1)+B;
if (y==0) {
for (int i=f; i<n; ++i) b[b_sz++]=a[i];
} else if (y==1) {
for (int i=0; i<f; ++i) b[b_sz++]=a[i];
for (int i=s; i<n; ++i) b[b_sz++]=a[i];
} else if (y==2) {
for (int i=0; i<s; ++i) b[b_sz++]=a[i];
for (int i=t; i<n; ++i) b[b_sz++]=a[i];
} else {
for (int i=0; i<t; ++i) b[b_sz++]=a[i];
}
forn(i,b_sz) a[i]=b[i];
a_sz=b_sz;
b_sz=0;
}
vector<int> tmp={a[0],a[1],a[2]};
a_sz=sq, b_sz=0;
for (int i=0; i<sq; ++i) a[i]=i;
while (a_sz>3) {
int n=a_sz;
int f=n/4+min(n%4,1);
int s=2*(n/4)+min(n%4,2);
int t=3*(n/4)+n%4;
int A=!receive(), B=!receive();
int y=(A<<1)+B;
if (y==0) {
for (int i=f; i<n; ++i) b[b_sz++]=a[i];
} else if (y==1) {
for (int i=0; i<f; ++i) b[b_sz++]=a[i];
for (int i=s; i<n; ++i) b[b_sz++]=a[i];
} else if (y==2) {
for (int i=0; i<s; ++i) b[b_sz++]=a[i];
for (int i=t; i<n; ++i) b[b_sz++]=a[i];
} else {
for (int i=0; i<t; ++i) b[b_sz++]=a[i];
}
forn(i,b_sz) a[i]=b[i];
a_sz=b_sz;
b_sz=0;
}
vector<int> paiu;
for (auto x:tmp) {
forn(i,3) paiu.push_back(x+a[i]*sq);
}
sort(paiu.begin(), paiu.end());
while (paiu.size()>3) {
vector<int> b;
int n=paiu.size();
int f=n/4 + min(n%4,1);
int s=2*(n/4) + min(n%4,2);
int t=3*(n/4) + min(n%4,3);
int A=!receive(), B=!receive();
int y=(A<<1)+B;
if (y==0) {
for (int i=f; i<n; ++i) b.push_back(paiu[i]);
} else if (y==1) {
forn(i,f) b.push_back(paiu[i]);
for (int i=s; i<n; ++i) b.push_back(paiu[i]);
} else if (y==2) {
forn(i,s) b.push_back(paiu[i]);
for (int i=t; i<n; ++i) b.push_back(paiu[i]);
} else {
forn(i,t) b.push_back(paiu[i]);
}
paiu=b;
}
int x=0;
forn(i,4) {
int f=receive();
x<<=1;
x+=f;
}
vector<int> ans;
for (auto v:dp[0][len-1][0]) if (v==x) ans.push_back(paiu[0]);
for (auto v:dp[0][len-1][1]) if (v==x) ans.push_back(paiu[0]);
for (auto v:dp[6][len-1][0]) if (v==x) ans.push_back(paiu[1]);
for (auto v:dp[6][len-1][1]) if (v==x) ans.push_back(paiu[1]);
for (auto v:dp[9][len-1][0]) if (v==x) ans.push_back(paiu[2]);
for (auto v:dp[9][len-1][1]) if (v==x) ans.push_back(paiu[2]);
if (ans.size()==1) ans.push_back(ans[0]);
for (auto &x:ans) x=min(x,n);
for (auto &x:ans) x=max(x,1);
return {ans[0],ans[1]};
}
void encode(int n, int x) {
if (n==3) {
if (x==1) {
send(0); send(0); send(0); send(0);
} else if (x==2) {
send(0); send(1); send(1); send(0);
} else {
send(1); send(0); send(0); send(1);
}
return;
}
int sq=sqrt(n)+1;
int first=x%sq;
int second=x/sq;
int save = x;
int a[40000], b[40000], a_sz=sq, b_sz=0;
for (int i=0; i<sq; ++i) a[i]=i;
//cout<<sq<<":\n";
x=first;
while (a_sz>3) {
int n=a_sz;
int f=n/4+min(n%4,1);
int s=2*(n/4)+min(n%4,2);
int t=3*(n/4)+n%4;
int l=0, r=a_sz-1;
while (l<r) {
int mid=(l+r+1)>>1;
if (a[mid]>x) r=mid-1;
else l=mid;
}
int A,B;
if (r<f) {
A=!send(0), B=!send(0);
} else if (r<s) {
A=!send(0), B=!send(1);
} else if (r<t) {
A=!send(1), B=!send(0);
} else {
A=!send(1), B=!send(1);
}
int y=(A<<1)+B;
//forn(i,a_sz) cout<<a[i]<<' '; cout<<'\n';
//cout<<f<<' '<<s<<' '<<t<<' '<<n<<" "<<y<<'\n';
if (y==0) {
for (int i=f; i<n; ++i) b[b_sz++]=a[i];
} else if (y==1) {
for (int i=0; i<f; ++i) b[b_sz++]=a[i];
for (int i=s; i<n; ++i) b[b_sz++]=a[i];
} else if (y==2) {
for (int i=0; i<s; ++i) b[b_sz++]=a[i];
for (int i=t; i<n; ++i) b[b_sz++]=a[i];
} else {
for (int i=0; i<t; ++i) b[b_sz++]=a[i];
}
forn(i,b_sz) a[i]=b[i];
a_sz=b_sz;
b_sz=0;
}
//cout<<a[0]<<' '<<a[1]<<' '<<a[2]<<'\n';
vector<int> tmp={a[0],a[1],a[2]};
a_sz=sq, b_sz=0;
for (int i=0; i<sq; ++i) a[i]=i;
x=second;
while (a_sz>3) {
int n=a_sz;
int f=n/4+min(n%4,1);
int s=2*(n/4)+min(n%4,2);
int t=3*(n/4)+n%4;
int l=0, r=a_sz-1;
while (l<r) {
int mid=(l+r+1)>>1;
if (a[mid]>x) r=mid-1;
else l=mid;
}
int A,B;
if (r<f) {
A=!send(0), B=!send(0);
} else if (r<s) {
A=!send(0), B=!send(1);
} else if (r<t) {
A=!send(1), B=!send(0);
} else {
A=!send(1), B=!send(1);
}
int y=(A<<1)+B;
if (y==0) {
for (int i=f; i<n; ++i) b[b_sz++]=a[i];
} else if (y==1) {
for (int i=0; i<f; ++i) b[b_sz++]=a[i];
for (int i=s; i<n; ++i) b[b_sz++]=a[i];
} else if (y==2) {
for (int i=0; i<s; ++i) b[b_sz++]=a[i];
for (int i=t; i<n; ++i) b[b_sz++]=a[i];
} else {
for (int i=0; i<t; ++i) b[b_sz++]=a[i];
}
forn(i,b_sz) a[i]=b[i];
a_sz=b_sz;
b_sz=0;
}
//cout<<a[0]<<' '<<a[1]<<' '<<a[2]<<'\n';
vector<int> paiu;
for (auto x:tmp) {
forn(i,3) paiu.push_back(x+a[i]*sq);
}
sort(paiu.begin(), paiu.end());
while (paiu.size()>3) {
vector<int> b;
int n=paiu.size();
int f=n/4 + min(n%4,1);
int s=2*(n/4) + min(n%4,2);
int t=3*(n/4) + min(n%4,3);
int l=0, r=n-1;
while (l<r) {
int mid=(l+r+1)>>1;
if (paiu[mid]>save) r=mid-1;
else l=mid;
}
int A,B;
if (r<f) {
A=!send(0), B=!send(0);
} else if (r<s) {
A=!send(0), B=!send(1);
} else if (r<t) {
A=!send(1), B=!send(0);
} else {
A=!send(1), B=!send(1);
}
int y=(A<<1)+B;
if (y==0) {
for (int i=f; i<n; ++i) b.push_back(paiu[i]);
} else if (y==1) {
forn(i,f) b.push_back(paiu[i]);
for (int i=s; i<n; ++i) b.push_back(paiu[i]);
} else if (y==2) {
forn(i,s) b.push_back(paiu[i]);
for (int i=t; i<n; ++i) b.push_back(paiu[i]);
} else {
forn(i,t) b.push_back(paiu[i]);
}
paiu=b;
}
if (paiu[0]==save) {
send(0); send(0); send(0); send(0);
} else if (paiu[1]==save) {
send(0); send(1); send(1); send(0);
} else {
send(1); send(0); send(0); send(1);
}
}
Compilation message
communication.cpp: In function 'std::pair<int, int> decode(int)':
communication.cpp:49:9: warning: unused variable 'first' [-Wunused-variable]
49 | int first=0;
| ^~~~~
communication.cpp:50:9: warning: unused variable 'second' [-Wunused-variable]
50 | int second=0;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
2376 KB |
Output is correct |
| 2 |
Correct |
17 ms |
2472 KB |
Output is correct |
| 3 |
Correct |
13 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
12 ms |
2340 KB |
Output is correct |
| 5 |
Correct |
16 ms |
2372 KB |
Output is correct |
| 6 |
Correct |
32 ms |
2980 KB |
Output is correct |
| 7 |
Correct |
52 ms |
2360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
885 ms |
2328 KB |
Output is partially correct |
| 2 |
Partially correct |
495 ms |
2368 KB |
Output is partially correct |
| 3 |
Partially correct |
687 ms |
2440 KB |
Output is partially correct |
| 4 |
Partially correct |
1141 ms |
2216 KB |
Output is partially correct |
| 5 |
Partially correct |
991 ms |
2300 KB |
Output is partially correct |
| 6 |
Partially correct |
893 ms |
2316 KB |
Output is partially correct |
| 7 |
Partially correct |
3241 ms |
2968 KB |
Output is partially correct |
| 8 |
Partially correct |
5127 ms |
4436 KB |
Output is partially correct |
| 9 |
Partially correct |
4386 ms |
3648 KB |
Output is partially correct |
| 10 |
Partially correct |
4542 ms |
3656 KB |
Output is partially correct |
| 11 |
Partially correct |
4176 ms |
3692 KB |
Output is partially correct |
| 12 |
Partially correct |
4514 ms |
3672 KB |
Output is partially correct |
| 13 |
Partially correct |
4450 ms |
3664 KB |
Output is partially correct |
| 14 |
Partially correct |
4534 ms |
3684 KB |
Output is partially correct |
| 15 |
Partially correct |
2562 ms |
2972 KB |
Output is partially correct |
| 16 |
Partially correct |
4811 ms |
3040 KB |
Output is partially correct |
| 17 |
Partially correct |
1394 ms |
3064 KB |
Output is partially correct |
| 18 |
Partially correct |
1123 ms |
3060 KB |
Output is partially correct |
| 19 |
Partially correct |
1215 ms |
2988 KB |
Output is partially correct |
| 20 |
Partially correct |
1086 ms |
3120 KB |
Output is partially correct |
| 21 |
Partially correct |
1199 ms |
3032 KB |
Output is partially correct |
| 22 |
Partially correct |
1251 ms |
2992 KB |
Output is partially correct |
| 23 |
Partially correct |
1851 ms |
3016 KB |
Output is partially correct |
| 24 |
Correct |
14 ms |
2360 KB |
Output is correct |
| 25 |
Correct |
17 ms |
2364 KB |
Output is correct |
| 26 |
Correct |
19 ms |
2392 KB |
Output is correct |
| 27 |
Correct |
14 ms |
2324 KB |
Output is correct |
| 28 |
Correct |
18 ms |
2416 KB |
Output is correct |
| 29 |
Correct |
32 ms |
3160 KB |
Output is correct |
| 30 |
Correct |
34 ms |
2408 KB |
Output is correct |
