Submission #823338

#	Time	Username	Problem	Language	Result	Execution time	Memory
823338		rainboy	Line Town (CCO23_day1problem3)	C11	13 / 25	56 ms	21016 KiB

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 (stderr)

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: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 3 / 3
• Subtask 4: 4 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 3
• Subtask 7: 0 / 2
• Subtask 8: 0 / 3