Submission #883178

#	Time	Username	Problem	Language	Result	Execution time	Memory
883178		Onur_Ilgaz	Coin Collecting (JOI19_ho_t4)	C++17	0 / 100	1 ms	348 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;

int32_t main(){
	fast
	int n;
	cin >> n;
	int N = n * 2;
	int ans = 0;
	vector <vector<int> > grid(n + 1, vector<int>(3));
	for(int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		int ydif = min(abs(b - 2), abs(b - 1));
		int xdif = min(abs(a - n), abs(a - 1));
		if(a >= 1 and a <= n) xdif = 0;
		ans += xdif + ydif;
		// cout << xdif << " " << ydif << "\n";
		int x, y;
		x = a + xdif;
		if(x < 1 or x > n) x = a - xdif;
		y = b + ydif;
		if(y < 1 or y > 2) y = b - ydif;
		grid[x][y]++;
	}
	// cout << ans << "\n";
	vector <pair<int,int> > point;
	array<vector<pair<int,int> >, 2> np;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= 2; j++) {
			// cout << grid[i][j] << " ";
			while(--grid[i][j] > 0) point.push_back({i, j});
		}
		// cout << "\n";
	}
	// cout << "\n";
	// ilk başta sadece i'lerini önemseyeceğiz
	int l = 0;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= 2; j++) {
			if(!grid[i][j]) continue;
			ans += abs(i - point[l].first);
			if(point[l].second != j) {
				np[j-1].push_back({i, point[l].first});
			}
			// her bir eşleştirilen ikiliyi çıktı ver
			// cout << i << "," << j << "  " << point[l].first << "," << point[l].second << "\n";
			l++;
		}
	}
	// cout << "\n";
	for(auto &it:np[0]) {
		if(it.first > it.second) swap(it.first, it.second);
		// cout << it.first << " " << it.second << "\n";
	}
	// cout << "\n";
	for(auto &it:np[1]) {
		if(it.first > it.second) swap(it.first, it.second);
		// cout << it.first << " " << it.second << "\n";
	}
	// cout << ans << "\n";
	int s1 = np[0].size(), s2 = np[1].size();
	l = 0; int r = 0;
	while(true) {
		if(l == s1) {
			ans += s2 - r;
			break;
		}
		if(r == s2) {
			ans += s1 - l;
			break;
		}
		int a = np[0][l].first, b = np[0][l].second;
		int x = np[1][r].first, y = np[1][r].second;
		if(a > x) swap(a, x), swap(b, y); // a <= x
		if(b >= x) {
			l++, r++;
		}
		else {
			ans++;
			a = np[0][l].first, b = np[0][l].second;
			x = np[1][r].first, y = np[1][r].second;
			if(a < x) l++;
			else r++;
		}
	}
	cout << ans << "\n";
}

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