Submission #119993

#	Time	Username	Problem	Language	Result	Execution time	Memory
119993		tutis	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	60 ms	6648 KiB

joi2019_ho_t4

/*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";
}

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