Submission #456276

#TimeUsernameProblemLanguageResultExecution timeMemory
456276MOUF_MAHMALATČVENK (COI15_cvenk)C++14
38 / 100
3062 ms84688 KiB
#include<bits/stdc++.h> #define all(s) s.begin(),s.end() using namespace std; typedef long long ll; ll n,a[100009],b[100009],sum=1e18; map<pair<ll,ll>,bool>mp; ll best(ll x,ll y,ll xx,ll yy) { ll ans=0,o; for(ll i=(1<<30); i; i>>=1) { if((i&x)==(i&xx)&&(i&y)==(i&yy)) continue; if((i&x)&&(i&xx)==0) { o=0; for(ll j=i; j; j>>=1) { o|=(j&x); if((j&y)) { ans+=j; y^=j; } } ans+=o-i+1; x^=i,x|=(i-1); } if((i&x)==0&&(i&xx)) { o=0; for(ll j=i; j; j>>=1) { o|=(j&xx); if((j&yy)) { ans+=j; yy^=j; } } ans+=o-i+1; xx^=i,xx|=(i-1); } if((i&y)&&(i&yy)==0) { o=0; for(ll j=i; j; j>>=1) { o|=(j&y); if((j&x)) { ans+=j; x^=j; } } ans+=o-i+1; y^=i,y|=(i-1); } if((i&y)==0&&(i&yy)) { o=0; for(ll j=i; j; j>>=1) { o|=(j&yy); if((j&xx)) { ans+=j; xx^=j; } } ans+=o-i+1; yy^=i,yy|=(i-1); } } return ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; mp[{0,0}]=1; for(ll i=0; i<n; i++) { cin>>a[i]>>b[i]; ll x=0,y=0; for(ll j=(1<<30);j;j>>=1) { if(a[i]&j) x+=j; else if(b[i]&j) y+=j; mp[{x,y}]=1; } } for(auto z:mp) { if(z.second==0) continue; ll xo=z.first.first; ll yo=z.first.second; ll op=0; for(ll i=0;i<n;i++) op+=best(xo,yo,a[i],b[i]); sum=min(sum,op); } cout<<sum; 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...