Submission #229500

#	Time	Username	Problem	Language	Result	Execution time	Memory
229500		hanagasumi	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	91 ms	10484 KiB

joi2019_ho_t4

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <complex>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <random>

#define ft first
#define sc second
#define pb push_back
#define len(v) (int)v.size()
#define int ll

using namespace std;
typedef long long ll;

int sgn(int x) {
	if(x < 0) 
		return -1;
	if(x == 0) 
		return 0;
	return 1;
}

signed main() {
	#ifdef PC
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;
	vector<vector<int>> have(n, vector<int> (2, 0));
	int ans = 0;
	for (int i = 0; i < 2 * n; i++) {
		int x, y;
		cin >> x >> y;
		if(y < 1) 
			ans += (1 - y), y = 1;
		if(y > 2) 
			ans += (y - 2), y = 2;
		if(x < 1) 
			ans += (1 - x), x = 1;
		if(x > n) 
			ans += (x - n), x = n;
		have[x - 1][y - 1]++;
	}

	// for (int j = 0; j < 2; j++) {
	// 	for (int i = 0; i < n; i++) {
	// 		cout << have[i][j] << " ";
	// 	}
	// 	cout << endl;
	// }

	// cout << ans << endl;
	// ans = 0;
	int top = 0, down = 0;
	for (int i = 0; i < n; i++) {
		top += have[i][0], down += have[i][1];
		top--, down--;
		// cout << i << " " << ans << "  " << top << " " << down << endl;
		if(top * down < 0) {
			int per = min(abs(top), abs(down));
			top += -1 * sgn(top) * per;
			down += -1 * sgn(down) * per;
			ans += per;
		}
		ans += abs(top) + abs(down);
	}
	cout << ans << '\n';
}

/*
if(have[i][0] == 0) {

			for (int j = i + 1; j < n; j++) {
				if(have[j][0] > 1) {
					cout << "X  " << i << " " << j << endl; 
					have[j][0]--;
					ans += (j - i);
					have[i][0] = 1;
					break;
				}
				if(j == i + 1 && down != 0) {
					down--;
					ans += 1;
					have[i][0] = 1;
					break;
				}
				if(have[j - 1][1] > 1) {
					have[j - 1][1]--;
					ans += (j - i);
					have[i][0] = 1;
					break;
				}
			}
			if(have[i][0] == 0) {
				ans += (n - i);
				have[i][0] = 1;
				if(i != n - 1)
					have[n - 1][1]--;
			}
			
		}
		if(have[i][1] == 0) {
			for (int j = i + 1; j < n; j++) {
				if(have[j][1] > 1) {
					have[j][1]--;
					ans += (j - i);
					have[i][1] = 1;
					break;
				}
				if(j == i + 1 && top != 0) {
					top--;
					ans += 1;
					have[i][1] = 1;
					break;
				}
				if(have[j - 1][0] > 1) {
					have[j - 1][0]--;
					ans += (j - i);
					have[i][1] = 1;
					break;
				}
			}
			if(have[i][1] == 0) {
				have[i][1] = 1;
				ans += (n - i);
				if(i != n - 1)
					have[n - 1][0]--;
			}
		}
		if(i == n - 1) 
			break;
		ans += top + down;
	}
	*/

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