#include <bits/stdc++.h>
#include "communication.h"
using namespace std;
vector<int> use(vector<int> &a,vector<int> &b,int x,int t){
sort(a.begin(),a.end());
sort(b.begin(),b.end());
int as=a.size();
int bs=b.size();
vector<int> la,ra,lb,rb;
if(as+bs<=2){
vector<int> z;
for(auto h:a){
z.push_back(h);
}
for(auto h:b){
z.push_back(h);
}
if(z.size()==1){
int u=z[0];
z.push_back(u);
}
return z;
}
else if(as+bs==3){
vector<int> g;
for(auto h:a){
g.push_back(h);
}
for(auto h:b){
g.push_back(h);
}
sort(g.begin(),g.end());
int u=-1;
for(int i=0;i<3;i++){
if(g[i]==x){
u=i;
}
}
if(t==0){
return g;
}
else{
string s[3]={"1111","0001","1000"};
if(u==-1){
string z;
for(int j=0;j<4;j++){
z+=char('0'+receive());
}
int flag=-1;
for(int i=0;i<3;i++){
int lst=0;
for(int j=0;j<4;j++){
if(s[i][j]!=z[j]){
if(lst){
flag=i;
break;
}
else{
lst=1;
}
}
else{
lst=0;
}
}
}
vector<int> ret;
for(int i=0;i<3;i++){
if(i!=flag){
ret.push_back(g[i]);
}
}
return ret;
}
else{
for(int i=0;i<4;i++){
send(int(s[u][i]-'0'));
}
return vector<int>();
}
}
}
int nxt=-1;
for(int i=0;i<as/2;i++){
if(a[i]==x){
nxt=0;
}
la.push_back(a[i]);
rb.push_back(a[i]);
}
for(int i=as/2;i<as;i++){
if(a[i]==x){
nxt=1;
}
ra.push_back(a[i]);
lb.push_back(a[i]);
}
for(int i=0;i<(bs+1)/2;i++){
if(b[i]==x){
nxt=0;
}
la.push_back(b[i]);
}
for(int i=(bs+1)/2;i<bs;i++){
if(b[i]==x){
nxt=1;
}
ra.push_back(b[i]);
}
int dd;
if(nxt==-1){
dd=receive();
}
else{
dd=send(nxt);
}
if(dd==0){
return use(la,lb,x,t);
}
else{
return use(ra,rb,x,t);
}
}
const int Bd=31623,Bd2=202;
vector<int> emp;
vector<int> solve2(int N,int X){
int a=-1,c=-1;
if(X!=-1){
a=X/Bd2;
c=X%Bd2;
}
vector<int> v(max(3,N/Bd2+2));
iota(v.begin(),v.end(),0);
auto e=use(v,emp,a,0);
vector<int> w(Bd2);
iota(w.begin(),w.end(),0);
auto f=use(w,emp,c,0);
vector<int> z;
for(auto h:e){
for(auto y:f){
if(h*Bd2+y<0 || h*Bd2+y>=N){
continue;
}
z.push_back(h*Bd2+y);
}
}
sort(z.begin(),z.end());
return z;
}
vector<int> solve(int N,int X){
int a=-1,c=-1;
if(X!=-1){
a=X/Bd;
c=X%Bd;
}
auto e=solve2(max(3,N/Bd+2),a);
auto f=solve2(Bd,c);
vector<int> z;
for(auto h:e){
for(auto y:f){
if(h*Bd+y<=0 || h*Bd+y>N){
continue;
}
z.push_back(h*Bd+y);
}
}
sort(z.begin(),z.end());
z.erase(unique(z.begin(),z.end()),z.end());
return use(z,emp,X,1);
}
void encode(int N,int X){
solve(N,X);
}
pair<int,int> decode(int N){
auto h=solve(N,-1);
int x=h.size();
return {h[0],h[min(x-1,1)]};
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
1860 KB |
Output is correct |
| 2 |
Correct |
79 ms |
1788 KB |
Output is correct |
| 3 |
Correct |
128 ms |
1784 KB |
Output is correct |
| 4 |
Correct |
60 ms |
1772 KB |
Output is correct |
| 5 |
Correct |
79 ms |
1776 KB |
Output is correct |
| 6 |
Correct |
221 ms |
1992 KB |
Output is correct |
| 7 |
Correct |
501 ms |
1832 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
498 ms |
1832 KB |
Output is partially correct |
| 2 |
Partially correct |
309 ms |
1864 KB |
Output is partially correct |
| 3 |
Partially correct |
365 ms |
1868 KB |
Output is partially correct |
| 4 |
Partially correct |
785 ms |
1856 KB |
Output is partially correct |
| 5 |
Partially correct |
652 ms |
1812 KB |
Output is partially correct |
| 6 |
Partially correct |
641 ms |
1772 KB |
Output is partially correct |
| 7 |
Partially correct |
2303 ms |
1984 KB |
Output is partially correct |
| 8 |
Partially correct |
3618 ms |
2428 KB |
Output is partially correct |
| 9 |
Partially correct |
3087 ms |
2252 KB |
Output is partially correct |
| 10 |
Partially correct |
3818 ms |
2232 KB |
Output is partially correct |
| 11 |
Partially correct |
3125 ms |
2232 KB |
Output is partially correct |
| 12 |
Partially correct |
3126 ms |
2244 KB |
Output is partially correct |
| 13 |
Partially correct |
3331 ms |
2200 KB |
Output is partially correct |
| 14 |
Partially correct |
3190 ms |
2240 KB |
Output is partially correct |
| 15 |
Partially correct |
1687 ms |
2056 KB |
Output is partially correct |
| 16 |
Partially correct |
3462 ms |
2004 KB |
Output is partially correct |
| 17 |
Partially correct |
894 ms |
2260 KB |
Output is partially correct |
| 18 |
Partially correct |
836 ms |
2028 KB |
Output is partially correct |
| 19 |
Partially correct |
974 ms |
2060 KB |
Output is partially correct |
| 20 |
Partially correct |
940 ms |
2092 KB |
Output is partially correct |
| 21 |
Partially correct |
945 ms |
2032 KB |
Output is partially correct |
| 22 |
Partially correct |
877 ms |
2088 KB |
Output is partially correct |
| 23 |
Partially correct |
1511 ms |
2024 KB |
Output is partially correct |
| 24 |
Correct |
51 ms |
1952 KB |
Output is correct |
| 25 |
Correct |
93 ms |
1864 KB |
Output is correct |
| 26 |
Correct |
157 ms |
1856 KB |
Output is correct |
| 27 |
Correct |
56 ms |
1944 KB |
Output is correct |
| 28 |
Correct |
88 ms |
1888 KB |
Output is correct |
| 29 |
Correct |
227 ms |
2164 KB |
Output is correct |
| 30 |
Correct |
493 ms |
1924 KB |
Output is correct |
