Submission #430251

#	Time	Username	Problem	Language	Result	Execution time	Memory
430251		MetalPower	Coin Collecting (JOI19_ho_t4)	C++14	0 / 100	1 ms	332 KiB

joi2019_ho_t4

#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
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63