Submission #846217

#TimeUsernameProblemLanguageResultExecution timeMemory
846217vjudge1ČVENK (COI15_cvenk)C++17
100 / 100
92 ms3668 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define tol(bi) (1LL<<((int)(bi))) int32_t main(){ int n;cin>>n; vector<pair<int,int>> arr(n); for (int i = 0; i < n; i++){ cin>>arr[i].first>>arr[i].second; } int crr = tol(32); int x = 0, y = 0; int ans = 0; while (crr>1){ int alt = 0; int sag = 0; int orta = 0; for (int i = 0; i < n; i++){ if (arr[i].first>x+crr/2-1) alt++; else if (arr[i].second>y+crr/2-1) sag++; else orta++; } //cout<<crr<<" "<<orta<<" "<<alt<<" "<<sag<<endl; if (alt>sag+orta){ for (int i = 0; i < n; i++){ if (arr[i].second>y+crr/2-1){ ans+=arr[i].first-x+arr[i].second-y; ans+=crr/2; arr[i].first=x+crr/2; arr[i].second=y; } else if (arr[i].first<=x+crr/2-1){ if (arr[i].second-y>arr[i].first-x){ ans+=arr[i].first-x+arr[i].second-y; ans+=crr/2; } else { int yuru = -1; for (int j = 1; j <= crr; j <<= 1){ int mo = (arr[i].first-x)%j; if (j>=arr[i].second-y+mo){ yuru=mo; break; } } assert(yuru!=-1); ans+=x+crr/2-arr[i].first+yuru*2; ans+=arr[i].second-y; //zurnanin zirt dedigi yer(done) } arr[i].first=x+crr/2; arr[i].second=y; } } x+=crr/2; } else if (sag>alt+orta){ for (int i = 0; i < n; i++){ if (arr[i].first>x+crr/2){ ans+=arr[i].first-x+arr[i].second-y; ans+=crr/2; arr[i].first=x; arr[i].second=y+crr/2; } else if (arr[i].second<=y+crr/2-1){ if (arr[i].first-x>arr[i].second-y){ ans+=arr[i].first-x+arr[i].second-y; ans+=crr/2; } else { int yuru = -1; for (int j = 1; j <= crr; j <<= 1){ int mo = (arr[i].second-y)%j; if (j>=arr[i].first-x+mo){ yuru=mo; break; } } assert(yuru!=-1); ans+=y+crr/2-arr[i].second+yuru*2; ans+=arr[i].first-x; //zurnanin zirt dedigi yer v2.0 } arr[i].first=x; arr[i].second=y+crr/2; } } y+=crr/2; } else { for (int i = 0; i < n; i++){ if (arr[i].first>x+crr/2-1){ ans+=arr[i].first-(x+crr/2-1)+arr[i].second-y; arr[i].first=x+crr/2-1; arr[i].second=y; } else if (arr[i].second>y+crr/2-1){ ans+=arr[i].first-x+arr[i].second-(y+crr/2-1); arr[i].first=x; arr[i].second=y+crr/2-1; } } } crr/=2; } //cout<<x<<" "<<y<<endl; cout<<ans<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...