Submission #224999

#TimeUsernameProblemLanguageResultExecution timeMemory
224999alishahali1382ČVENK (COI15_cvenk)C++14
60 / 100
3065 ms1536 KiB
#include <bits/stdc++.h> #pragma GCC optimize ("O2") #pragma GCC optimize ("unroll-loops") //#pragma GCC optimize("no-stack-protector,fast-math") using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<pii, int> piii; typedef pair<ll, ll> pll; #define debug(x) cerr<<#x<<'='<<(x)<<endl; #define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl; #define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl; #define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;} #define all(x) x.begin(), x.end() #define pb push_back #define kill(x) return cout<<x<<'\n', 0; const ld eps=1e-7; const int inf=1000000010; const ll INF=10000000000000010LL; const int mod=1000000007; const int MAXN=100010, LOG=20; ll n, m, k, u, v, x, y, t, a, b, ans=INF; pii A[MAXN]; int P[MAXN]; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); inline pii GetPar(pii p, int k){ int x=p.first, y=p.second; while (k){ int xx=(x&-x), yy=(y&-y); if (!xx) xx=2*inf; if (!yy) yy=2*inf; int tmp=min(k, min(xx, yy)); k-=tmp; if (xx<yy) x-=tmp; else y-=tmp; } return {x, y}; } inline ll GetH(pii p){ return p.first+p.second; } inline pii Lca(pii x, pii y){ if (GetH(x)<GetH(y)) swap(x, y); x=GetPar(x, GetH(x)-GetH(y)); if (x==y) return x; // :) int dwn=0, up=GetH(x); while (up-dwn>1){ int mid=(dwn+up)>>1; if (GetPar(x, mid)==GetPar(y, mid)) up=mid; else dwn=mid; } return GetPar(x, up); } inline ll Dist(pii x, pii y){ return GetH(x)+GetH(y)-2*GetH(Lca(x, y)); } inline int GetSz(pii p){ // O(n.lg) int res=0; for (int i=1; i<=n; i++) if (GetH(p)<=GetH(A[i])) res+=(GetPar(A[i], GetH(A[i])-GetH(p))==p); return res; } inline void check(pii v){ // O(n.lg^2) ll sum=0; for (int i=1; i<=n; i++){ sum+=Dist(A[i], v); if (sum>=ans) return ; // :) } ans=min(ans, sum); } inline void check2(pii v){ // O(n.lg^2) int dwn=-1, up=GetH(v); while (up-dwn>1){ int mid=(dwn+up)>>1; if (GetSz(GetPar(v, mid))*2>n) up=mid; else dwn=mid; } check(GetPar(v, up)); } int main(){ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); cin>>n; for (int i=1; i<=n; i++) cin>>A[i].first>>A[i].second, P[i]=i; shuffle(P+1, P+n+1, rng); for (int i=1; i<=min(n, 8ll); i++) check2(A[P[i]]); cout<<ans<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...