oj.uz

Submission #883135

# Submission time Handle Problem Language Result Execution time Memory
883135 2023-12-04T15:44:11 Z Onur_Ilgaz 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;

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}), grid[i][j]--;
		}
		// 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++) {
			ans += abs(i - point[l].first);
			if(point[l].second != j) {
				np[j-1].push_back({i, point[l].first});
			}
			l++;
		}
	}
	// cout << "\n";
	for(auto &it:point) {
		// cout << it.first << " " << it.second << "\n";
	}
	// 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";
}

Compilation message

joi2019_ho_t4.cpp: In function 'int32_t main()':
joi2019_ho_t4.cpp:51:12: warning: unused variable 'it' [-Wunused-variable]
   51 |  for(auto &it:point) {
      |            ^~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 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 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 344 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 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 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 344 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 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 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 344 KB Output isn't correct
10 Halted 0 ms 0 KB -