제출 #101728

#제출 시각아이디문제언어결과실행 시간메모리
101728KCSCCoin Collecting (JOI19_ho_t4)C++14
100 / 100
267 ms6256 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...