oj.uz

Submission #846359

# Submission time Handle Problem Language Result Execution time Memory
846359 2023-09-07T14:00:49 Z vjudge1 ČVENK (COI15_cvenk) C++17
0 / 100
 52 ms 1880 KB 
#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.0

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

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 Incorrect 34 ms 1880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

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