Labyrintti

input/code.cpp: In function 'bool sees(ll, ll, ll, ll)':
input/code.cpp:16:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size()-1; ++i) {
                  ~~^~~~~~~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:68:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); ++i) {
                  ~~^~~~~~~~~~

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

const ll INF = (1LL<<62);

vector<pair<ll, ll>> v;

ll dist(ll y0, ll x0, ll y1, ll x1) {
	return abs(y0-y1) + abs(x0-x1);
}

bool sees(ll y0, ll x0, ll y1, ll x1) {
	for (int i = 0; i < v.size()-1; ++i) {
		auto a = v[i];
		auto b = v[i+1];
		ll wx0 = a.first;
		ll wx1 = b.first;
		ll wy0 = a.second;
		ll wy1 = b.second;
		if (wx0 > wx1) swap(wx0, wx1);
		if (wy0 > wy1) swap(wy0, wy1);

		if (i%2 == 0) {
			// horizontal
			if (y0 == wy0 && y1 == wy0 && min(x0, x1) < wx0 && max(x0, x1) > wx1) return false;
			if (min(y0, y1) < wy0 && max(y0, y1) > wy0 && wx0 <= x0 && x0 <= wx1 && wx0 <= x1 && x1 <= wx1) return false;
		}
		else {
			// vertical
			if (x0 == wx0 && x1 == wx0 && min(y0, y1) < wy0 && max(y0, y1) > wy1) return false;
			if (min(x0, x1) < wx0 && max(x0, x1) > wx0 && wy0 <= y0 && y0 <= wy1 && wy0 <= y1 && y1 <= wy1) return false;
		}
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	ll y0, x0, y1, x1;
	cin >> y0 >> x0 >> y1 >> x1;

	ll cx = 0;
	ll cy = 0;
	for (int i = 1; i < 63; ++i) {
		v.push_back({cx, cy});
		if (i%4 == 1) {
			cx += (1LL<<i);
		}
		else if (i%4 == 2) {
			cy -= (1LL<<i);
		}
		else if (i%4 == 3) {
			cx -= (1LL<<i);
		}
		else {
			cy += (1LL<<i);
		}
	}
	vector<pair<ll, ll>> cpos;
	cpos.push_back({0, -1});

	int dy[4] = {0, 1, 0, -1};
	int dx[4] = {-1, 0, 1, 0};
	for (int i = 0; i < v.size(); ++i) {
		cpos.push_back({v[i].first+dx[i%4], v[i].second+dy[i%4]});
	}

	int apos = 0, bpos = 0;
	while (!sees(y0, x0, cpos[apos].second, cpos[apos].first)) apos++;
	while (!sees(y1, x1, cpos[bpos].second, cpos[bpos].first)) bpos++;
	
	// assume that a is outer
	if (apos < bpos) {
		swap(apos, bpos);
		swap(x0, x1);
		swap(y0, y1);
	}

	ll res = 0;
	if (apos != bpos) {
		apos++;
		if (sees(y1, x1, cpos[bpos+1].second, cpos[bpos+1].first)) bpos++;
	}
	// cout << "starting pos: " << y0 << ", " << x0 << endl;
	while (apos != bpos) {
		apos--;
		ll cdist = dist(y0, x0, cpos[apos].second, cpos[apos].first);
		res += cdist;
		y0 = cpos[apos].second;
		x0 = cpos[apos].first;
		// cout << "moved " << cdist << " units, new pos " << y0 << ", " << x0 << endl;
	}

	res += dist(y0, x0, y1, x1);

	cout << res << "\n";
	return 0;
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: WRONG ANSWER

Test 6

Group: 2

Verdict: WRONG ANSWER

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: WRONG ANSWER

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: WRONG ANSWER

Test 12

Group: 3

Verdict: WRONG ANSWER

Test 13

Group: 3

Verdict: WRONG ANSWER

Test 14

Group: 3

Verdict: WRONG ANSWER

Test 15

Group: 3

Verdict: WRONG ANSWER