Submission #823334

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
823334	2023-08-12T10:51:16 Z	rainboy	Line Town (CCO23_day1problem3)	C	0 / 25	0 ms	340 KB

Main

#include <stdio.h>

#define N	500000
#define INF	0x3f3f3f3f3f3f3f3fLL

long long min(long long a, long long b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int main() {
	static int aa[N], ii1[N], ii2[N], kkp1[N + 1], kkp2[N + 1], kkq1[N + 1], kkq2[N + 1];
	static long long vvp[N + 1], vvq[N + 1];
	int n, n0, n1, n2, i, l1, l2, k, k1, k2;
	long long v, ans;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &aa[i]);
		if (i % 2 != 0)
			aa[i] = -aa[i];
	}
	n1 = 0, n2 = 0;
	for (i = 0; i < n; i++)
		if (aa[i] == -1)
			ii1[n1++] = i;
		else if (aa[i] == 1)
			ii2[n2++] = i;
	n0 = n - n1 - n2;
	kkp1[0] = k1 = 0, kkp2[0] = k2 = 0, vvp[0] = v = 0;
	for (k = 1, l1 = 0, l2 = 0; k <= n1 + n2; k++) {
		if ((k - 1) % 2 == 0) {
			if (k1 < n1) {
				i = ii1[k1];
				while (l2 < n2 && ii2[l2] < i)
					l2++;
				v += i - k1 - min(l2, k2);
			}
			k1++;
		} else {
			if (k2 < n2) {
				i = ii2[k2];
				while (l1 < n1 && ii1[l1] < i)
					l1++;
				v += i - k2 - min(l1, k1);
			}
			k2++;
		}
		kkp1[k] = k1, kkp2[k] = k2, vvp[k] = v;
	}
	kkq1[n1 + n2] = k1 = n1, kkq2[n1 + n2] = k2 = n2, vvq[n1 + n2] = v = 0;
	for (k = n1 + n2 - 1, l1 = n1, l2 = n2; k >= 0; k--) {
		if ((n0 + k) % 2 == 0) {
			k1--;
			if (k1 >= 0) {
				i = ii1[k1];
				while (l2 > 0 && ii2[l2 - 1] >= i)
					l2--;
				v += n0 - (i - k1 - l2) + max(l2 - k2, 0);
			}
		} else {
			k2--;
			if (k2 >= 0) {
				i = ii2[k2];
				while (l1 > 0 && ii1[l1 - 1] >= i)
					l1--;
				v += n0 - (i - k2 - l1) + max(l1 - k1, 0);
			}
		}
		kkq1[k] = k1, kkq2[k] = k2, vvq[k] = v;
	}
	ans = INF;
	for (k = 0; k <= n1 + n2; k++)
		if (kkp1[k] == kkq1[k] && kkp2[k] == kkq2[k])
			ans = min(ans, vvp[k] + vvq[k]);
	if (ans == INF)
		ans = -1;
	printf("%lld\n", ans);
	return 0;
}

Compilation message

Main.c: In function 'main':
Main.c:15:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
Main.c:17:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	Output is correct
2	Incorrect	288 KB	Output isn't correct
3	Halted	0 KB	-

Subtask #2
0 / 3.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	Output is correct
2	Incorrect	288 KB	Output isn't correct
3	Halted	0 KB	-

Subtask #3
0 / 3.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	Output is correct
2	Incorrect	288 KB	Output isn't correct
3	Halted	0 KB	-

Subtask #4
0 / 4.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	Output is correct
2	Incorrect	288 KB	Output isn't correct
3	Halted	0 KB	-

Subtask #5
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	292 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	292 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 2.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	Output is correct
2	Incorrect	288 KB	Output isn't correct
3	Halted	0 KB	-

Subtask #8
0 / 3.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	Output is correct
2	Incorrect	288 KB	Output isn't correct
3	Halted	0 KB	-