Submission #846454

#	Time	Username	Problem	Language	Result	Execution time	Memory
846454		NotLinux	ČVENK (COI15_cvenk)	C++17	0 / 100	3039 ms	344 KiB

cvenk

#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
• Subtask 2: 0 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40