Submission #846438

#	Time	Username	Problem	Language	Result	Execution time	Memory
846438		NotLinux	ČVENK (COI15_cvenk)	C++17	0 / 100	3049 ms	348 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;
	}
	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();
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40