Submission #332844

#	Time	Username	Problem	Language	Result	Execution time	Memory
332844		ace_in_the_hole	Coin Collecting (JOI19_ho_t4)	C++14	100 / 100	61 ms	5868 KiB

joi2019_ho_t4

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

typedef long long Int;
const int MAX = 2e5 + 500;
int cnt[MAX][2];

int SIGN(int x) {
	if (x) return x / abs(x); return 0;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	Int answer = 0;
	
	int n;	cin >> n;
	
	for (int i = 0; i < n + n; i++) {
		int x, y;
		cin >> x >> y;
		if (x < 1) answer += 1 - x, x = 1;
		if (x > n) answer += x - n, x = n;
		if (y < 1) answer += 1 - y, y = 1;
		if (y > 2) answer += y - 2, y = 2;
//		cerr << '(' << x << ',' << y << ")\n";
		cnt[--x][--y]++;
	}
	
	for (int i = 0; i < n; i++) for (int j = 0; j < 2; j++) {
		cnt[i][j]--;
//		cerr << "(" << i + 1 << ',' << j + 1 << ") gives " << cnt[i][j] << '\n';	
	}

	for (int i = 0; i + 1 < n; i++) {
		if (SIGN(cnt[i][0]) == SIGN(cnt[i][1])) {
//			cerr << cnt[i][0] << '/' << cnt[i][1] << '\n';
			answer += abs(cnt[i][0]) + abs(cnt[i][1]);
//			cerr << "ans += " << abs(cnt[i][0]) + abs(cnt[i][1]) << '\n';
			cnt[i + 1][0] += cnt[i][0];
			cnt[i + 1][1] += cnt[i][1];
		} else {
//			cerr << "steps to zero(s) : " << min(abs(cnt[i][0]), abs(cnt[i][1])) << '\n';
			if (abs(cnt[i][0]) <= abs(cnt[i][1])) {
				answer += abs(cnt[i][0]);
				cnt[i][1] += cnt[i][0];
				answer += abs(cnt[i][1]);
				cnt[i + 1][1] += cnt[i][1];
			} else {
				answer += abs(cnt[i][1]);
				cnt[i][0] += cnt[i][1];
				answer += abs(cnt[i][0]);
				cnt[i + 1][0] += cnt[i][0];
			}
		}
	}
	
	assert(cnt[n - 1][0] + cnt[n - 1][1] == 0);
	answer += abs(cnt[n - 1][0]);
	cout << answer;
}
/*
5
1000000000 1000000000
-1000000000 1000000000
-1000000000 -1000000000
1000000000 -1000000000
-1 -5
-2 2
2 8
4 7
-2 5
7 3

4
2 1
2 1
2 1
3 1
3 1
3 1
3 1
3 1
*/

Compilation message (stderr)

joi2019_ho_t4.cpp: In function 'int SIGN(int)':
joi2019_ho_t4.cpp:9:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    9 |  if (x) return x / abs(x); return 0;
      |  ^~
joi2019_ho_t4.cpp:9:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
    9 |  if (x) return x / abs(x); return 0;
      |                            ^~~~~~

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