Submission #846359

#	Time	Username	Problem	Language	Result	Execution time	Memory
846359		vjudge1	ČVENK (COI15_cvenk)	C++17	0 / 100	52 ms	1880 KiB

cvenk

#include <bits/stdc++.h>
using namespace std;

#define int int64_t

#define all(x) (x).begin(),(x).end()

#define x first
#define y second

int computePath(pair<int, int> p, pair<int, int> p2){
	
	auto pc = p;
	auto pc2 = p2;

	int ans = 1e16;

	for (int i = 1; i < 40; i++){

		p2 = pc2;
		
		for (int j = 1; j < 40; j++){
			
			auto s1 = p2;

			p2.x -= (p2.x)%(1<<j);
			p2.y -= (p2.y)%(1<<j);
			
			auto s2 = p2;

			if (s1.x == s2.x) {
				if (s1.x == p.x && p.y >= s2.y && p.y <= s1.y) {
					ans = min(ans, abs(pc.x - p.x) + abs(pc.y - p.y) + abs(pc2.x - p.x) + abs(pc2.y - p.y));
					//cout << p.x << ' ' << p.y << endl;
					//cout << abs(pc.x - p.x) + abs(pc.y - p.y) + abs(pc2.x - p.x) + abs(pc2.y - p.y) << endl;
				}
			}
			else{
				if (s1.y == p.y && p.x >= s2.x && p.x <= s1.x) {
					ans = min(ans, abs(pc.x - p.x) + abs(pc.y - p.y) + abs(pc2.x - p.x) + abs(pc2.y - p.y));
					//cout << p.x << ' ' << p.y << endl;
					//cout << abs(pc.x - p.x) + abs(pc.y - p.y) + abs(pc2.x - p.x) + abs(pc2.y - p.y) << endl;
				}
			}

		}

		p.x -= (p.x)%(1<<i);
		p.y -= (p.y)%(1<<i);

		//cout << p.x << ' ' << p.y << endl;
	}

	return ans;
}


signed main() {
	//ios_base::sync_with_stdio(false);
	//cin.tie();
	
	int n; cin >> n;

	vector<pair<int, int>> v(n);
	for (auto& i: v) cin >> i.x >> i.y;

	cout << computePath(v[0], v[1]) << endl;
}




/*
	for (auto& i: path1){
		cout << i.x << ' ' << i.y << endl;
	}
	cout << endl;
	for (auto& i: path2){
		cout << i.x << ' ' << i.y << endl;
	}
	*/

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