| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 651668 | TimDee | Flight to the Ford (BOI22_communication) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include"communication.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for (int i=0; i<n; ++i)
const int PAIU=15;
pair<int,int> decode(int n) {
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;
//cout<<sq<<":\n";
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;
//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;
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;
}
//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 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;
}
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)));
}
}
}
//for (auto v:dp[0][len-1][0]) if (v==x) a[a_sz++]=paiu[0];
//for (auto v:dp[0][len-1][1]) if (v==x) a[a_sz++]=paiu[0];
//for (auto v:dp[6][len-1][0]) if (v==x) a[a_sz++]=paiu[1];
//for (auto v:dp[6][len-1][1]) if (v==x) a[a_sz++]=paiu[1];
//for (auto v:dp[9][len-1][0]) if (v==x) a[a_sz++]=paiu[2];
//for (auto v:dp[9][len-1][1]) if (v==x) a[a_sz++]=paiu[2];
//x=0;
//forn(i,4) {
// int f=receive();
// x<<=1; x+=f;
//}
//cout<<x<<" "<<paiu[0]<<' '<<paiu[1]<<' '<<paiu[2]<<'\n';
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]};
}