Submission #883309

# Submission time Handle Problem Language Result Execution time Memory
883309 2023-12-05T06:29:00 Z vjudge1 Coin Collecting (JOI19_ho_t4) C++17
0 / 100
1 ms 348 KB
#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;
random_device rd;
mt19937 mt(rd());

int32_t main(){
	fast
	int n;
	cin >> n;
	int N = n * 2;
	int ans = 0;
	vector <vector<int> > grid(n + 1, vector<int>(3));
	vector <pair<int, int> > p;
	for(int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		p.push_back({a, b});
	}
	shuffle(p.begin(), p.end(), mt);
	for(int i = 0; i < N; i++) {
		int a = p[i].first, b = p[i].second;
		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";
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Incorrect 1 ms 348 KB Output isn't correct
19 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Incorrect 1 ms 348 KB Output isn't correct
19 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Incorrect 1 ms 348 KB Output isn't correct
19 Halted 0 ms 0 KB -