Submission #498710

#	Time	Username	Problem	Language	Result	Execution time	Memory
498710		Ierus	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	243 ms	5096 KiB

joi2019_ho_t4

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("unroll-loops,Ofast,O3")
#pragma GCC target("avx,avx2,fma")
#define F first
#define S second
#define sz(x) (int)x.size()
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define NFS ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
const int N = 1e5+12;
int n, used[N][4];
long long ans = 0;
int main(){
	cin >> n;
	for(int i = 1; i <= 2 * n; ++i){
		int x, y;
		cin >> x >> y;
		if(y > 2){
			ans += y - 2;
			y = 2;
		}
		if(y < 1){
			ans += abs(y-1);
			y = 1;
		}
		if(x > n){
			ans += x - n;
			x = n;
		}
		if(x < 1){
			ans += abs(x-1);
			x = 1;
		}
		++used[x][y];
	}
	int cnt1 = 0, cnt2 = 0;
	for(int i = 1; i <= n; ++i){
		cnt1 += used[i][1] - 1;
		cnt2 += used[i][2] - 1;
		int mn = min(abs(cnt1), abs(cnt2));
		if(cnt1 < 0 && cnt2 > 0){
			cnt1 += mn;
			cnt2 -= mn;
			ans += mn;
		}else if(cnt1 > 0 && cnt2 < 0){
			cnt2 += mn;
			cnt1 -= mn;
			ans += mn;
		}
		ans += abs(cnt1) + abs(cnt2);
	}
	cout << ans;
}

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