Submission #679671

#	Time	Username	Problem	Language	Result	Execution time	Memory
679671		ethening	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	56 ms	6092 KiB

joi2019_ho_t4

#include "bits/stdc++.h"
using namespace std;
using ll = long long;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n;
	vector cnt(3, vector(n + 5, 0));
	ll ans = 0;
	for (int i = 1; i <= 2 * n; i++) {
		ll x, y;
		cin >> x >> y;
		ll tarx, tary;
		if (x >= 1 && x <= n) {
			tarx = x;
		}
		else {
			if (x < 1) tarx = 1;
			else tarx = n;
		}
		if (y >= 1 && y <= 2) {
			tary = y;
		}
		else {
			if (y < 1) tary = 1;
			else tary = 2;
		}
		++cnt[tary][tarx];
		ans += abs(x - tarx) + abs(y - tary);
	}
	
	int diff1 = 0;
	int diff2 = 0;
	
	for (int i = 1; i <= n; i++) {
		diff1 += cnt[1][i] - 1;
		diff2 += cnt[2][i] - 1;
		if (diff1 > 0 && diff2 < 0) {
			int d = min(diff1, -diff2);
			ans += d;
			diff1 -= d;
			diff2 += d;
		}
		else if (diff1 < 0 && diff2 > 0) {
			int d = min(diff2, -diff1);
			ans += d;
			diff1 += d;
			diff2 -= d;
		}
		ans += abs(diff1) + abs(diff2);
	}

	cout << ans << endl;
}

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 63 / 63