| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 846435 |
2023-09-07T14:42:03 Z |
vjudge1 |
ČVENK (COI15_cvenk) |
C++17 |
|
3000 ms |
344 KB |
#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_popcount(a.first) + __builtin_popcount(a.second);
int cntb = __builtin_popcount(b.first) + __builtin_popcount(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 |
| 1 |
Execution timed out |
3050 ms |
344 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3043 ms |
344 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
