이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,ans = 0;
pair < int , int > par(pair < int, int > a){
if((a.first & -a.first) < (a.second & -a.second) and (a.first & -a.first) != 0){
ans += a.first & -a.first;
a.first -= a.first & -a.first;
}
else if((a.second & -a.second) != 0){
ans += a.second & -a.second;
a.second -= a.second & -a.second;
}
else {
ans += a.first & -a.first;
a.first -= a.first & -a.first;
}
return a;
}
int dist(pair < int , int > a , pair < int , int > b){
int ret = 0;
int cnta = __builtin_popcountll(a.first) + __builtin_popcountll(a.second);
int cntb = __builtin_popcountll(b.first) + __builtin_popcountll(b.second);
if(cnta < cntb)swap(a,b);
int diff = cntb - cnta;
while(diff--){
pair < int , int > newa = par(a);
ret += a.first - newa.first + a.second - newa.second;
a = newa;
}
while(a != b){
pair < int , int > newa = par(a);
pair < int , int > newb = par(b);
if(par(a) == par(b)){
if(a.first == b.first){
ret -= min(a.second,b.second) - newa.second + 1;
}
else if(a.second == b.second){
ret -= min(a.first,b.first) - newa.first + 1;
}
}
ret += a.first - newa.first + a.second - newa.second;
ret += b.first - newb.first + b.second - newb.second;
a = newa;
b = newb;
}
return ret;
}
/*
int dist(pair < int , int > a , pair < int , int > b){//a -> b
pair < int , int > c = lca(a,b);
//int ret = c.first + c.second ;
return ret;
}*/
void solve(){
int n;cin >> n;
pair < int , int > a,b;
cin >> a.first >> a.second;
cin >> b.first >> b.second;
cout << dist(a,b) << endl;
/*
cin >> n;
deque < pair < int , int > > v(n);
for(auto &inp : v)cin >> inp.first >> inp.second;
while(true){
bool bl = 1;
v.push_front({0,0});
sort(v.begin() , v.end());
cout << "v : ";for(auto itr : v)cout << itr.first << "," << itr.second << " ";cout << endl;
for(int i = 0;i<((int)v.size()-1);i++){
if((dist({0,0},v[i]) + dist(v[i],v[i+1])) != (dist({0,0},v[i+1]))){
bl = 0;
break;
}
}
v.pop_front();
cout << bl << endl;
if(bl)break;
int mini = 1e18 + 7 , change = 0;
for(int i = 0;i<n;i++){
int val = min(v[i].first & -v[i].first , v[i].second & -v[i].second);
//cout << i << " ::: " << (v[i].first & -v[i].first) << " " << (v[i].second & -v[i].second) << endl;
if((v[i].first & -v[i].first) == 0)val = v[i].second & -v[i].second;
else if((v[i].second & -v[i].second) == 0)val = v[i].first & -v[i].first;
if(mini > val){
mini = val;
change = i;
}
}
//cout << mini << " " << change << endl;
v[change] = par(v[change]);
}
cout << ans << endl;
vector < vector < int > > t;
for(auto itr : v){
t.push_back({itr.first + itr.second , itr.first , itr.second});
}
sort(t.begin() , t.end());
pair < int , int > cent = {t[n/2][1] , t[n/2][2]};
cout << "center : " << cent.first << " " << cent.second << endl;
for(auto &itr : t){
ans += dist({itr[1],itr[2]},cent);
cout << itr[1] << " " << itr[2] << " -> " << ans << endl;
}
cout << ans << endl;*/
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int testcase = 1;//cin >> testcase;
while(testcase--)solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |