| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 652058 | 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"
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define forn(i,n) for (int i=0; i<n; ++i)
int V[3000000]; int ptr=0; int asz=0;
void brut(int x, int n, int v=0, int i=0, int l=0) {
if (i>=n) {V[ptr++]=v; return;}
int b=(x>>i)&1;
brut(x,n,v+(b<<i),i+1,0);
if (l==0) brut(x,n,v+((!b)<<i),i+1,1);
}
vector<int> get_possible(int n) {
ll x=0, q=0;
forn(i,29) {
q=receive();
x+=q<<i;
}
brut(x,29);
vector<int> b;
for (int j=0; j<ptr; ++j) {
int x=V[j];
if (x>=n) continue;
for (ll i=0; i+x<n; i+=1ll<<29) {
b.push_back(x);
}
}
sort(b.begin(), b.end());
ptr=0;
return b;
}
vector<int> dequery(vector<int>&a,int bit) {
int x=0, q;
forn(i,bit) x+=receive()<<i;
brut(x,bit);
vector<int> b;
for (int j=0; j<ptr; ++j) {
int x=V[j];
if (x>=a.size()) continue;
for (int i=0; i+x<a.size(); i+=(1<<bit)) {
b.push_back(a[i+x]);
}
}
sort(b.begin(), b.end());
ptr=0;
return b;
}
pair<int,int> decode(int n) {
if (n>3) return{1,1};
vector<int> a=get_possible(n); //for (auto x:a) cout<<x<<' '; cout<<'\n';
a=dequery(a,21);
a=dequery(a,15);
a=dequery(a,11);
a=dequery(a,8);
a=dequery(a,6);
a=dequery(a,4);
a=dequery(a,3);
a=dequery(a,4); //for (auto x:a) cout<<x<<' '; cout<<'\n';
a=dequery(a,3); //for (auto x:a) cout<<x<<' '; cout<<'\n';
a=dequery(a,2); //for (auto x:a) cout<<x<<' '; cout<<'\n';
a=dequery(a,2); //for (auto x:a) cout<<x<<' '; cout<<'\n';
if (a.size()==1) return{a[0]+1,a[0]+1};
if (a.size()==2) return{a[0]+1,a[1]+1};
assert(a.size()==3);
int q,x=0;
q=receive();
x+=q<<0;
q=receive();
x+=q<<1;
q=receive();
x+=q<<2;
q=receive();
x+=q<<3;
vector<int> ans;
vector<int> A={0,1,5,10,9,8,2,4};
vector<int> B={1,8,9,11,13,3,12,0};
vector<int> C={6,15,2,4,12,3,7,14};
for (auto v:A) if (v==x) ans.push_back(a[0]);
for (auto v:B) if (v==x) ans.push_back(a[2]);
for (auto v:C) if (v==x) ans.push_back(a[1]);
if (ans.size()==1) return {ans[0]+1,ans[0]+1};
return {ans[0]+1,ans[1]+1};
}
int Send(int x, int bit) {
ll ret=0;
forn(i,bit) ret+=send((x>>i)&1)<<i;
return ret;
}
void get_possible(int[]&a,int n, int x) {
x=Send(x,29);
brut(x,29);
vector<int> b;
int cnt=0;
for (int j=0; j<ptr; ++j) {
int x=V[j];
if (x>=n) continue;
for (ll i=0; i+x<n; i+=1ll<<29) {
b.push_back(x);
}
}
sort(b.begin(), b.end());
ptr=0;
forn(i,b.size()) a[asz++]=b[i];
}
vector<int> query(vector<int>&a,int x,int bit) {
int l=0,r=a.size()-1;
while (l<r) {
int mid=(l+r+1)>>1;
if (a[mid]>x) r=mid-1;
else l=mid;
}
r=Send(r,bit);
brut(r,bit);
vector<int> b;
for (int j=0; j<ptr; ++j) {
int x=V[j];
if (x>=a.size()) continue;
for (int i=0; i+x<a.size(); i+=(1<<bit)) {
b.push_back(a[i+x]);
}
}
sort(b.begin(), b.end());
ptr=0;
return b;
}
void encode(int n, int x) {
--x;
get_possible(a,n,x); //for (auto x:a) cout<<x<<' '; cout<<'\n';
if (n>3) return;
a=query(a,x,21);
a=query(a,x,15);
a=query(a,x,11);
a=query(a,x,8);
a=query(a,x,6);
a=query(a,x,4);
a=query(a,x,3);
a=query(a,x,4); //for (auto x:a) cout<<x<<' '; cout<<'\n';
a=query(a,x,3); //for (auto x:a) cout<<x<<' '; cout<<'\n';
a=query(a,x,2); //for (auto x:a) cout<<x<<' '; cout<<'\n';
a=query(a,x,2); //for (auto x:a) cout<<x<<' '; cout<<'\n';
if (a.size()<3) return;
assert(a.size()==3);
int v=0,b=0;;
if (x==a[0]) {
b=send(0);
v+=b<<0;
b=send(0);
v+=b<<1;
b=send(0);
v+=b<<2;
b=send(0);
v+=b<<3;
} else if (x==a[1]) {
b=send(0);
v+=b<<0;
b=send(1);
v+=b<<1;
b=send(1);
v+=b<<2;
b=send(0);
v+=b<<3;
} else {
b=send(1);
v+=b<<0;
b=send(0);
v+=b<<1;
b=send(0);
v+=b<<2;
b=send(1);
v+=b<<3;
}
}