Submission #1126433

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126433		dubabuba	Coin Collecting (JOI19_ho_t4)	C++20	0 / 100	3 ms	3400 KiB

joi2019_ho_t4

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

#define int long long
typedef const int cint;
typedef pair<int, int> pii;
#define ff first
#define ss second

const int mxn = 2e5 + 10;
int n, cnt[10][mxn], ans;

void near(cint x, cint y, int &X, int &Y) {
	X = x, Y = y;
	if(x < 1) X = 1;
	if(x > n) X = n;
	if(y < 1) Y = 1;
	if(y > 2) Y = 2;
}

int dis(int x, int y, int X, int Y) {
	return abs(x - X) + abs(y - Y);
}

void debug() {
	for(int x = 1; x <= n; x++)
		cout << cnt[1][x] << ' ';
	cout << endl;
	for(int x = 1; x <= n; x++)
		cout << cnt[2][x] << ' ';
	cout << endl;
}

void solve(int cnt[]) {
	// cout << "solving...\n";
	map<int, int> mp;
	for(int x = 1; x <= n; x++) {
		// cout << cnt[x] << ' ';
		if(cnt[x] > 0) {
			mp[x] = cnt[x];
		}
	}
	// cout << endl;

	for(int x = 1; x <= n; x++) {
		if(cnt[x] > -1) continue;
		while(cnt[x] < 0) {
			pii p = *mp.begin();
			ans += abs(p.ff - x);
			if(p.ss > 1)
				mp[p.ff]--;
			else
				mp.erase(mp.find(p.ff));
			cnt[x]++;
		}
	}
}

int32_t main() {
	cin >> n;
	memset(cnt[1], -1, sizeof cnt[1]);
	memset(cnt[2], -1, sizeof cnt[2]);
	for(int i = 0; i < 2 * n; i++) {
		int x, y, nx, ny;
		cin >> x >> y;
		near(x, y, nx, ny);
		cnt[ny][nx]++;
		ans += dis(x, y, nx, ny);
	}

	// debug();
	// cout << ans << endl;

	int cnt1 = 0, cnt2 = 0;
	int ext1 = 0, ext2 = 0;
	for(int x = 1; x <= n; x++) {
		if(cnt[1][x] == -1) cnt1++;
		else ext1 += cnt[1][x];

		if(cnt[2][x] == -1) cnt2++;
		else ext2 += cnt[2][x];

	}


	int diff = ext1 - cnt1;
	if(diff < 0) {
		swap(cnt[1], cnt[2]);
		diff = -diff;
	}

	// debug();
	// cout << ans << endl;

	for(int x = 1; x <= n; x++)
		cnt[3][x] = cnt[1][x] + cnt[2][x];
	solve(cnt[3]);
	ans += diff;

	cout << ans << endl;
	return 0;
}

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