This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 18;
struct Line{
ll x, y;
void re(){
cin >> x >> y;
}
};
ll r(ll n){
if(n==0) return 1e18;
return n & -n;
}
ll f(ll x, ll y, ll cost, vector<array<ll, 3>> &g){
if(x==y){
g.pb({0, 0, cost});
return cost;
}
g.pb({x, y, cost});
if(r(x) < r(y)){
return cost + f(x - r(x), y, r(x), g);
}
return cost + f(x, y - r(y), r(y), g);
}
int n;
Line a[N];
void solve(){
cin >> n;
for(int i = 0; i < n; ++i){
a[i].re();
}
vector<array<ll, 3>> X, Y;
ll ans = 0;
ans += f(a[0].x, a[0].y, 0, X);
ans += f(a[1].x, a[1].y, 0, Y);
reverse(all(X));
reverse(all(Y));
// for(auto k: X){
// cout << k[0] << ' ' << k[1] << '\n';
// }
// en;
// for(auto k: Y){
// cout << k[0] << ' ' << k[1] << '\n';
// }
// en;
Y.pb(Y.back());
X.pb(X.back());
for(int i = 0; i < min(Y.size(), X.size()); ++i){
if(Y[i][0] == X[i][0] && Y[i][1] == X[i][1]){
ans -= X[i][2] + Y[i][2];
}else{
ans += abs(X[i][0] - Y[i][0]) + abs(Y[i][1] - X[i][1]);
break;
}
}
cout << ans;
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// cin >> tt;
while(tt--){
solve();
// en;
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
Compilation message (stderr)
cvenk.cpp: In function 'void solve()':
cvenk.cpp:58:20: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
58 | for(int i = 0; i < min(Y.size(), X.size()); ++i){
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~
cvenk.cpp: In function 'int main()':
cvenk.cpp:72:15: warning: unused variable 'aa' [-Wunused-variable]
72 | int tt = 1, aa;
| ^~
# | 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... |