제출 #119993

#제출 시각아이디문제언어결과실행 시간메모리
119993tutisCoin Collecting (JOI19_ho_t4)C++17
100 / 100
60 ms6648 KiB
/*input
3
0 0
0 4
4 0
2 1
2 5
-1 1

*/
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
ll k[100001][2];
int main()
{
	ios_base::sync_with_stdio(false);
	ll n;
	cin >> n;
	ll ans = 0;
	for (ll i = 0; i < 2 * n; i++)
	{
		ll x, y;
		cin >> x >> y;
		x--;
		y--;
		if (x < 0)
		{
			ans += -x;
			x = 0;
		}
		if (x >= n)
		{
			ans += x - (n - 1);
			x = n - 1;
		}
		if (y < 0)
		{
			ans += -y;
			y = 0;
		}
		if (y > 1)
		{
			ans += y - 1;
			y = 1;
		}
		k[x][y]++;
	}
	for (int x = 0; x < n; x++)
	{
		if (k[x][0] < 1 && k[x][1] > 1)
		{
			ll m = min(abs(k[x][0] - 1), abs(k[x][1] - 1));
			k[x][0] += m;
			k[x][1] -= m;
			ans += m;
		}
		if (k[x][0] > 1 && k[x][1] < 1)
		{
			ll m = min(abs(k[x][0] - 1), abs(k[x][1] - 1));
			k[x][0] -= m;
			k[x][1] += m;
			ans += m;
		}
		if (k[x][0] == 0)
		{
			if (k[x][1] > 1)
			{
				k[x][1]--;
				k[x][0]++;
				ans++;
			}
		}
		if (k[x][1] == 0)
		{
			if (k[x][0] > 1)
			{
				k[x][0]--;
				k[x][1]++;
				ans++;
			}
		}
		if (k[x][0] > 1)
		{
			ans += k[x][0] - 1;
			k[x + 1][0] += k[x][0] - 1;
			k[x][0] = 1;
		}
		if (k[x][1] > 1)
		{
			ans += k[x][1] - 1;
			k[x + 1][1] += k[x][1] - 1;
			k[x][1] = 1;
		}
		if (k[x][0] <= 0)
		{
			ll dx = abs(k[x][0] - 1);
			k[x][0] += dx;
			k[x + 1][0] -= dx;
			ans += dx;
		}
		if (k[x][1] <= 0)
		{
			ll dx = abs(k[x][1] - 1);
			k[x][1] += dx;
			k[x + 1][1] -= dx;
			ans += dx;
		}
	}
	cout << ans << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...