Submission #101728

#	Time	Username	Problem	Language	Result	Execution time	Memory
101728		KCSC	Coin Collecting (JOI19_ho_t4)	C++14	100 / 100	267 ms	6256 KiB

joi2019_ho_t4

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

const int DIM = 100005;

int cnt[DIM][3];
vector<int> qry[3], bal[3];

int main(void) {
#ifdef HOME
	freopen("coins.in", "r", stdin);
	freopen("coins.out", "w", stdout);
#endif
	int n; cin >> n;
	long long ans = 0;
	for (int i = 1; i <= n * 2; ++i) {
		int x, y; cin >> x >> y;
		if (x < 1) { ans += 1 - x; x = 1; }
		if (x > n) { ans += x - n; x = n; }
		if (y < 1) { ans += 1 - y; y = 1; }
		if (y > 2) { ans += y - 2; y = 2; } 
		++cnt[x][y]; }
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= 2; ++j) {		
			qry[j].push_back(i);
			for (; cnt[i][j]; --cnt[i][j]) {
				bal[j].push_back(i); } }
		// solve as many columns with balls placed on the same line
		for (int j = 1; j <= 2; ++j) {
			while (qry[j].size() and bal[j].size()) {
				int p1 = qry[j].back(), p2 = bal[j].back();
				qry[j].pop_back(); bal[j].pop_back(); ans += abs(p1 - p2); } }
		// solve as many columns with balls placed on the opposite line
		for (int j = 1; j <= 2; ++j) {
			while (qry[j].size() and bal[3 - j].size()) {
				int p1 = qry[j].back(), p2 = bal[3 - j].back();
				qry[j].pop_back(); bal[3 - j].pop_back(); ans += abs(p1 - p2) + 1; } } }
	cout << ans << endl;
	return 0; }

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