oj.uz

Submission #430251

# Submission time Handle Problem Language Result Execution time Memory
430251 2021-06-16T12:30:03 Z MetalPower Coin Collecting (JOI19_ho_t4) C++14
0 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int MX = 2e5 + 100;

ll ans = 0;
int N, x[MX], y[MX], cnt[MX][5];

int absol(int a){
	return a < 0 ? -a : a;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N;

	for(int i = 0; i < 2 * N; i++) cin >> x[i] >> y[i];

	// first compress the positions such that it will all lie on the N * 2 area
		// 1 <= X <= N and 1 <= Y <= 2

	for(int i = 0; i < 2 * N; i++){
		if(x[i] < 1){
			ans += 1 - x[i]; x[i] = 1;
		}else if(x[i] > N){
			ans += x[i] - N; x[i] = N;
		}

		if(y[i] < 1){
			ans += 1 - y[i]; y[i] = 1;
		}else if(y[i] > 2){
			ans += y[i] - 2; y[i] = 2;
		}

		cnt[x[i]][y[i]]++;
	}

	// Now we can solve this problem as
	// There are 2 * N coins located on the N * 2 area

	int empty1 = 0, empty2 = 0;

	// the number of empty cells on row 1 and the number of empty cells on row 2

	// Let us solve for only N cells, ignoring the second row

	/*	
		int cells = 0;
		// cells are the number of cells that needs to be moved
		// negative cells meaning from right to left
		// positive cells meaning from left to right
		for(int i = 1; i <= N; i++){
			cells += cnt[i] - 1;
			ans += abs(cells);
		}
	*/

	// it is easy to solve only the first row
	// now the only move we need to handle is moving up or down

	// it is optimal to move up or down if first and second row are opposite to each other
	// this is because when it is opposite to each other
		// we add the ans by cells
		// but then calculating moving left and right will be decreased by 2 * cells

	for(int i = 1; i <= N; i++){
		empty1 += cnt[i][1] - 1; empty2 += cnt[i][2] - 1;

		bool pos1 = empty1 < 0, pos2 = empty2 < 0;

		if(pos1 != pos2){
			// switch
			int cells = min(absol(pos1), absol(pos2));

			if(pos1){
				empty1 += cells;
				empty2 -= cells;
			}else{
				empty1 -= cells;
				empty2 += cells;
			}

			ans += cells;
		}

		ans += absol(empty1) + absol(empty2);
	}

	cout << ans << '\n';
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -