Submission #1205933

#TimeUsernameProblemLanguageResultExecution timeMemory
1205933lightonFlight to the Ford (BOI22_communication)C++20
15 / 100
1328 ms134740 KiB
#include"communication.h" #include<bits/stdc++.h> #define pb push_back #define all(v) v.begin(),v.end() #define forf(i,s,e) for(int i = s; i<=e; i++) #define forb(i,s,e) for(int i = s; i>=e; i--) #define idx(i,v) (int)(lower_bound(all(v),i)-v.begin()) #define comp(v) v.erase(unique(all(v)),v.end()) #define sz(v) (int)v.size() #define fs first #define se second #define SP << " " << #define LN << "\n" #define IO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false); using namespace std; typedef long long ll; ll inf = 1e18; vector<int> message[4] = {{0,0,0,0}, {0,1,1,0}, {1,0,0,1}, {1,1,1,1}}; vector<int> contrast(vector<int> R){ vector<int> ret; forf(x,0,3){ int f = 1; forf(i,0,2) if(R[i]!=message[x][i] && R[i+1]!=message[x][i+1]) f = 0; if(f) ret.pb(x); } return ret; } vector<int> fib[31]; void fibdfs(int n, int now, int i){ if(i == -1){ fib[n].pb(now); return;} fibdfs(n,now,i-1); if(!(now&(1<<(i+1)))) fibdfs(n,now^(1<<i),i-1); } void getfib(int n){ if(sz(fib[n])) return; fibdfs(n,0,n-1); } int piv = 100; vector<int> enc(int N, int X){ if(N==2) return {0,1}; if(N==1) return {0}; if(N>=piv) { int n = 1; while ((1 << n) < N) n++; getfib(n); int R = 0; forf(i, 0, n - 1) R += send((X & (1 << i)) ? 1 : 0) * (1 << i); int nx = idx(X ^ R, fib[n]); auto v = enc(sz(fib[n]), nx); vector<int> ret; for (int i : v) if(i < sz(fib[n]) && (R ^ fib[n][i]) < N) ret.pb(R ^ fib[n][i]); return ret; } else{ int p[5]; forf(i,0,4) p[i] = (double)N / 4 * i; int I; forf(i,0,4) if(X>=p[i]) I = i; vector<int> R; forf(i,0,3) R.pb(send(message[I][i])); vector<pair<int,int> > intv; int nN=0,nX=0; for(auto i : contrast(R)) intv.pb({p[i],p[i+1]}), nN += p[i+1]-p[i]; if(X < intv[0].se) nX = X-intv[0].fs; else nX = intv[0].se-intv[0].fs + X-intv[1].fs; vector<int> res = enc(nN,nX); vector<int> ret; for(auto i : res){ if(i < intv[0].se-intv[0].fs) ret.pb(intv[0].fs+i); else ret.pb(intv[1].fs+ i-(intv[0].se-intv[0].fs)); } return ret; } } vector<int> dec(int N){ if(N==2) return {0,1}; if(N==1) return {0}; if(N>=piv) { int n = 1; while ((1 << n) < N) n++; getfib(n); int R = 0; forf(i, 0, n - 1) R += receive() * (1 << i); auto v = dec(sz(fib[n])); vector<int> ret; for (int i : v) if(i < sz(fib[n]) && (R ^ fib[n][i]) < N) ret.pb(R ^ fib[n][i]); return ret; } else{ int p[5]; forf(i,0,4) p[i] = (double)N / 4 * i; vector<int> R; forf(i,0,3) R.pb(receive()); vector<pair<int,int> > intv; int nN=0; for(auto i : contrast(R)) intv.pb({p[i],p[i+1]}), nN += p[i+1]-p[i]; vector<int> res = dec(nN); vector<int> ret; for(auto i : res){ if(i < intv[0].se-intv[0].fs) ret.pb(intv[0].fs+i); else ret.pb(intv[1].fs+ i-(intv[0].se-intv[0].fs)); } return ret; } } void encode(int N, int X) { auto trash = enc(N,X-1); } std::pair<int, int> decode(int N) { vector<int> ans = dec(N); sort(all(ans)); if(sz(ans)== 1) return {ans[0]+1,ans[0]+1}; else return {ans[0]+1, ans[1]+1}; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...