Submission #533022

#	Time	Username	Problem	Language	Result	Execution time	Memory
533022		amunduzbaev	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	99 ms	16644 KiB

joi2019_ho_t4

#include "bits/stdc++.h"
using namespace std;

#define ar array
#define int long long

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n; n <<= 1;
	vector<ar<int, 2>> a(n), b(n);
	int res = 0;
	vector<vector<int>> cc(n / 2 + 1, vector<int>(3));
	for(int i=0;i<n;i++){
		cin>>a[i][0]>>a[i][1];
		b[i][0] = i / 2 + 1, b[i][1] = (i&1) + 1;
		if(a[i][1] > 2) res += (a[i][1] - 2), a[i][1] = 2;
		if(a[i][1] < 1) res += (1 - a[i][1]), a[i][1] = 1;
		if(a[i][0] < 1) res += (1 - a[i][0]), a[i][0] = 1;
		if(a[i][0] > n/2) res += (a[i][0] - n/2), a[i][0] = n/2;
		cc[a[i][0]][a[i][1]]++;
	}
	
	ar<int, 3> dp {};
	for(int i=1;i<=n/2;i++){
		for(int j=1;j<=2;j++){
			dp[j] += (cc[i][j] - 1);
		}
		
		if(dp[1] * 1ll * dp[2] < 0){
			int t = min(abs(dp[1]), abs(dp[2]));
			if(dp[1] > 0) dp[1] -= t, dp[2] += t;
			else dp[2] -= t, dp[1] += t;
			res += t;
		}
		
		res += abs(dp[1]), res += abs(dp[2]);
	}
	
	cout<<res<<"\n";
}

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