oj.uz

Submission #846454

# Submission time Handle Problem Language Result Execution time Memory
846454 2023-09-07T14:57:43 Z NotLinux ČVENK (COI15_cvenk) C++17
0 / 100
 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_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;
	}
	//cout << a.first << "," << a.second << " " << b.first << "," << b.second << " => " << ret << endl;
	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 -= 2 * (min(a.second,b.second) - newa.second);
			}
			else if(a.second == b.second){
				ret -= 2 * (min(a.first,b.first) - newa.first);
			}
		}
		ret += a.first - newa.first + a.second - newa.second;
		ret += b.first - newb.first + b.second - newb.second;
		a = newa;
		b = newb;
		//cout << a.first << "," << a.second << " " << b.first << "," << b.second << " => " << ret << endl;
	}
	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;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3017 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3039 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -