Submission #1037249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037249		beaconmc	ČVENK (COI15_cvenk)	C++14	17 / 100	0 ms	432 KiB

cvenk

#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;



vector<ll> lca(vector<ll> a, vector<ll> b){
	if (a[0]+a[1] < b[0] + b[1]) swap(a,b);
	map<vector<ll>, vector<ll>> prev;
	set<vector<ll>> stuff;
	stuff.insert(a);
	prev[a] = {-1,-1};



	while (a[0] != 0 || a[1] != 0){
		
		ll fira=1000, firb=1000;
		FOR(i,0,31) if ((1<<i)&a[0]){fira = i; break;}
		FOR(i,0,31) if ((1<<i)&a[1]){firb = i; break;}



		if (fira > firb){
			vector<ll> old = a;
			if (fira==1000){
				a = {0,0};
			}
			else a[1] -= (a[1] % (1<<fira));
			
			
			stuff.insert(a);
			prev[a] = old;
		}else{
			vector<ll> old = a;
			if (firb==1000){
				a = {0,0};
			}
			else a[0] -= (a[0] % (1<<firb));
			stuff.insert(a);
			prev[a] = old;
		}
	}



	if (stuff.count(b)) return b;

	while (b[0] != 0 || b[1] != 0){
		ll fira=1000, firb=1000;
		FOR(i,0,31) if ((1<<i)&b[0]){fira = i; break;}
		FOR(i,0,31) if ((1<<i)&b[1]){firb = i; break;}


		if (fira > firb){
			vector<ll> old = b;
			if (fira==1000) b = {0,0};
			else b[1] -= (b[1] % (1<<fira));
			if (stuff.count(b)){
				if ((b[0] == old[0] && old[0] == prev[b][0]) || (b[1] == old[1] && old[1] == prev[b][1])) return old;
				return b;
			}

		}else{
			vector<ll> old = b;
			if (firb==1000) b = {0,0};
			else b[0] -= (b[0] % (1<<firb));
			if (stuff.count(b)){
				if ((b[0] == old[0] && old[0] == prev[b][0]) || (b[1] == old[1] && old[1] == prev[b][1])) return old;
				return b;
			}
		}
	}


	return {};
}
int main(){
	ll n;
	cin >> n;

	vector<ll> A(2);
	vector<ll> B(2);
	cin >> A[0] >> A[1] >> B[0] >> B[1];
	
	vector<ll> sus = lca(A,B);


	cout << A[0]+A[1]+B[0]+B[1]-sus[0]*2-sus[1]*2;


}

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