Submission #221662

#	Time	Username	Problem	Language	Result	Execution time	Memory
221662		hanagasumi	Coin Collecting (JOI19_ho_t4)	C++17	0 / 100	5 ms	512 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;



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;
	int top = 0, down = 0;
	for (int i = 0; i < n; i++) {
		top += have[i][0], down += have[i][1];
		// cout << i << " " << top << " " << down << " " << ans << endl;
		have[i][0] = 0, have[i][1] = 0;
		if(top > 0) {
			have[i][0] = 1;
			top--;
		}
		if(down > 0) {
			have[i][1] = 1;
			down--;
		}
		// cout << have[i][0] << " " << have[i][1] << endl;
		if(have[i][0] == 0) {

			for (int j = i + 1; j < n; j++) {
				if(have[j][0] > 1) {
					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;
				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);
				have[n - 1][0]--;
			}
		}
		if(i == n - 1) 
			break;
		ans += top + down;
	}
	cout << ans << '\n';
}

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