QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#302492#6627. Line TownDJ20066 32ms17384kbC++171.6kb2024-01-10 22:19:532024-01-10 22:19:53

Judging History

你现在查看的是最新测评结果

  • [2024-01-10 22:19:53]
  • 评测
  • 测评结果:6
  • 用时:32ms
  • 内存:17384kb
  • [2024-01-10 22:19:53]
  • 提交

answer

#include <bits/stdc++.h>

void cmax(long long &x, long long y) {
	if (x < y) x = y;
}

void cmin(long long &x, long long y) {
	if (x > y) x = y;
}

const long long INF = 1e18;

const int maxn = 5e5;

int n;
int h[maxn + 5];

int s1[maxn + 5];
int s2[maxn + 5];

long long f[maxn + 5];
long long g[maxn + 5];

int main() {
	std::ios::sync_with_stdio(false);
	
	std::cin >> n;
	for (int i = 1; i <= n; i++)
		std::cin >> h[i];
	
	for (int i = 1; i <= n; i++) {
		s1[i] = s1[i - 1];
		if (h[i] == 1) {
			if (i & 1) {
				s1[i]++;
			} else {
				s1[i]--;
			}
		}
	}
	
	for (int i = n; i >= 1; i--) {
		s2[i] = s2[i + 1];
		if (h[i] == -1) {
			if (i & 1) {
				s2[i]++;
			} else {
				s2[i]--;
			}
		}
	}
	
	for (int i = 0; i <= n + 1; i++)
		f[i] = g[i] = INF;
	
	f[0] = 0;
	for (int i = 1; i <= n; i++) {
		f[i] = f[i - 1];
		if (h[i] == 1) {
			if (i & 1) {
				if (s1[i - 1] >= 0) {
					f[i] -= i;
				} else {
					f[i] += i;
				}
			} else {
				if (s1[i - 1] <= 0) {
					f[i] -= i;
				} else {
					f[i] += i;
				}
			}
		}
	}
	
	g[n + 1] = 0;
	for (int i = n; i >= 1; i--) {
		g[i] = g[i + 1];
		if (h[i] == -1) {
			if (i & 1) {
				if (s2[i + 1] >= 0) {
					g[i] += i;
				} else {
					g[i] -= i;
				}
			} else {
				if (s2[i + 1] <= 0) {
					g[i] += i;
				} else {
					g[i] -= i;
				}
			}
		}
	}
	
	long long ans = INF;
	for (int i = 0; i <= n; i++) {
		if (s1[i] == 0 && s2[i + 1] == 0) {
			cmin(ans, f[i] + g[i + 1]);
		}
	}
	
	if (ans == INF) ans = -1;
	std::cout << ans << "\n";
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 3
Accepted

Test #1:

score: 3
Accepted
time: 0ms
memory: 7680kb

input:

10
1 1 1 1 1 -1 -1 -1 1 -1

output:

-1

result:

ok 1 number(s): "-1"

Test #2:

score: 0
Accepted
time: 1ms
memory: 7676kb

input:

10
1 1 1 1 1 1 -1 1 1 -1

output:

3

result:

ok 1 number(s): "3"

Test #3:

score: 0
Accepted
time: 1ms
memory: 7732kb

input:

1
-1

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 1ms
memory: 7724kb

input:

2000
1 -1 -1 -1 -1 -1 1 -1 1 1 1 -1 -1 -1 1 1 -1 1 1 -1 -1 1 -1 -1 1 -1 1 -1 1 1 -1 1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 1 1 -1 -1 1 -1 -1 -1 1 -1 -1 1 1 -1 -1 -1 1 1 -1 1 -1 1 1 -1 -1 -1 1 1 1 -1 1 1 -1 -1 1 -1 1 1 1 1 -1 -1 -1 1 1 -1 -1 1 1 1 -1 -1 -1 -1 1 -1 -1 1 1 -1 1 -1 1 -1 -1 -1 1 -1 -1 ...

output:

15146

result:

ok 1 number(s): "15146"

Test #5:

score: 0
Accepted
time: 1ms
memory: 7764kb

input:

2000
-1 -1 1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 1 -1 1 1 -1 1 1 1 -1 1 1 1 1 1 -1 -1 -1 -1 1 1 -1 -1 -1 1 -1 -1 1 1 1 1 -1 -1 1 -1 -1 1 -1 -1 -1 1 1 1 1 1 -1 -1 -1 -1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 -1 -1 -1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 -1 -1 -1 -1 1 -1 1 1 -1 1 1 1 -1 1 1 -1 -1 -1 ...

output:

24933

result:

ok 1 number(s): "24933"

Test #6:

score: 0
Accepted
time: 1ms
memory: 7796kb

input:

2000
1 1 -1 -1 -1 -1 1 1 -1 1 -1 1 1 1 -1 -1 -1 1 -1 -1 1 1 -1 -1 1 1 -1 1 1 -1 1 1 -1 1 1 1 -1 -1 1 -1 -1 1 -1 -1 1 -1 1 -1 1 1 1 -1 -1 -1 -1 1 -1 1 -1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 -1 1 1 1 -1 1 1 1 1 1 -1 -1 -1 1 1 -1 1 1 -1 -1 1 -1 1 -1 -1 1 1 1 -1 -1 1 1 -1 1 -1 -1 -1 1 -1 -1 -1 1 -1 1 -1 -1 1 -...

output:

18090

result:

ok 1 number(s): "18090"

Test #7:

score: 0
Accepted
time: 1ms
memory: 7744kb

input:

2000
-1 -1 -1 -1 -1 1 1 -1 -1 -1 1 1 -1 -1 1 -1 1 1 1 1 -1 -1 1 1 1 1 -1 -1 -1 -1 1 1 1 1 1 -1 1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 1 1 -1 1 -1 -1 1 1 -1 1 1 -1 -1 -1 -1 1 -1 1 1 -1 -1 1 -1 1 1 -1 -1 1 1 -1 1 -1 -1 1 -1 1 1 -1 -1 -1 1 -1 -1 1 1 1 -1 1 1 -1 -1 -1 1 -1 -1 1 -1 1 1 1 -1 1 -1 -1 1 1 1...

output:

-1

result:

ok 1 number(s): "-1"

Test #8:

score: 0
Accepted
time: 0ms
memory: 7816kb

input:

2000
-1 1 -1 1 1 -1 -1 1 1 -1 1 1 -1 1 -1 -1 1 -1 1 1 1 1 -1 -1 -1 1 -1 1 -1 -1 1 1 -1 1 -1 -1 1 -1 1 -1 1 1 1 1 1 -1 -1 -1 1 -1 -1 -1 -1 1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 -1 -1 1 -1 1 1 1 -1 1 1 1 1 -1 -1 -1 1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 1 -1 1 -1 -1 -1 1 -1 -1 -1 ...

output:

9973

result:

ok 1 number(s): "9973"

Test #9:

score: 0
Accepted
time: 0ms
memory: 7748kb

input:

2000
-1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 ...

output:

499500

result:

ok 1 number(s): "499500"

Test #10:

score: 0
Accepted
time: 1ms
memory: 5772kb

input:

2000
1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...

output:

499500

result:

ok 1 number(s): "499500"

Test #11:

score: 0
Accepted
time: 1ms
memory: 7776kb

input:

1999
1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...

output:

499500

result:

ok 1 number(s): "499500"

Test #12:

score: 0
Accepted
time: 1ms
memory: 7824kb

input:

1997
1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...

output:

498501

result:

ok 1 number(s): "498501"

Test #13:

score: 0
Accepted
time: 1ms
memory: 7704kb

input:

2000
1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...

output:

-1

result:

ok 1 number(s): "-1"

Subtask #2:

score: 3
Accepted

Dependency #1:

100%
Accepted

Test #14:

score: 3
Accepted
time: 1ms
memory: 7740kb

input:

1
1

output:

0

result:

ok 1 number(s): "0"

Test #15:

score: 0
Accepted
time: 31ms
memory: 17252kb

input:

500000
1 -1 -1 -1 -1 1 -1 -1 1 -1 1 -1 -1 -1 -1 1 -1 1 1 -1 1 -1 1 1 1 -1 -1 1 -1 1 1 1 1 1 -1 -1 -1 1 -1 1 1 1 1 1 1 1 -1 -1 1 1 -1 1 1 1 -1 1 -1 1 1 -1 -1 1 -1 -1 -1 1 -1 1 -1 -1 -1 1 -1 1 1 -1 1 1 1 -1 1 1 1 1 1 1 1 1 1 -1 1 1 1 -1 -1 -1 1 -1 1 -1 1 1 1 1 -1 1 -1 -1 1 1 -1 1 1 1 1 -1 1 1 -1 -1 1 ...

output:

29737766

result:

ok 1 number(s): "29737766"

Test #16:

score: 0
Accepted
time: 29ms
memory: 17384kb

input:

500000
1 -1 -1 1 1 1 1 1 1 1 1 1 -1 1 -1 -1 1 -1 1 -1 1 1 -1 1 -1 -1 1 -1 1 -1 -1 1 -1 -1 -1 -1 1 -1 1 -1 1 -1 -1 1 -1 -1 1 -1 1 1 1 1 -1 1 -1 1 -1 1 1 1 -1 1 -1 -1 -1 -1 -1 1 1 -1 1 -1 -1 -1 1 1 1 -1 -1 -1 -1 -1 -1 1 1 -1 1 -1 -1 1 1 -1 -1 1 -1 -1 -1 1 -1 1 1 1 1 -1 1 1 -1 1 -1 1 1 -1 1 -1 -1 -1 -1...

output:

66957355

result:

ok 1 number(s): "66957355"

Test #17:

score: 0
Accepted
time: 28ms
memory: 17344kb

input:

500000
1 -1 1 1 1 -1 1 1 -1 1 1 1 -1 -1 -1 1 1 1 1 -1 -1 -1 -1 1 1 -1 -1 -1 1 -1 -1 -1 1 1 -1 1 -1 1 1 -1 -1 -1 -1 1 1 1 1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 1 -1 -1 1 1 1 -1 -1 -1 -1 1 1 1 1 -1 1 1 -1 -1 1 1 -1 -1 1 -1 1 1 -1 1 -1 -1 1 -1 1 1 1 -1 1 1 -1 -1 1 1 1 -1 1 -1 1 -1 -1 -1 -1 -1 1 -1 1...

output:

50480873

result:

ok 1 number(s): "50480873"

Test #18:

score: 0
Accepted
time: 29ms
memory: 17244kb

input:

500000
-1 1 1 -1 1 1 -1 1 1 -1 1 1 1 -1 -1 1 -1 1 -1 -1 1 -1 1 -1 -1 1 1 -1 -1 1 1 -1 1 1 1 -1 1 1 -1 1 1 -1 1 1 -1 1 1 1 1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 1 -1 1 1 -1 1 1 -1 1 1 1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 1 -1 1 1 -1 -1 1 -1 -1 1 -1 1 -1 1 -1 -1 1 1 1 -1 1 -1 1 -1 1 1 1 1 1 -1 1 -1 1 1 1 -1 -1 -1 -1...

output:

-1

result:

ok 1 number(s): "-1"

Test #19:

score: 0
Accepted
time: 32ms
memory: 17360kb

input:

500000
1 1 1 1 -1 -1 -1 1 -1 1 1 -1 -1 1 1 1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 1 -1 1 -1 1 1 -1 1 1 -1 -1 -1 -1 -1 -1 1 1 -1 1 1 -1 -1 -1 -1 -1 1 1 1 -1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 -1 1 1 1 -1 -1 -1 1 1 1 -1 1 1 1 1 1 1 -1 1 -1 -1 -1 1 -1 -1 1 -1 1 -1 -1 1 -1 1 1 1 1 1 1 -1 -1 -1 -1 1 1 -1 1 1 1...

output:

90473670

result:

ok 1 number(s): "90473670"

Test #20:

score: 0
Accepted
time: 24ms
memory: 17324kb

input:

500000
-1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...

output:

31249875000

result:

ok 1 number(s): "31249875000"

Test #21:

score: 0
Accepted
time: 15ms
memory: 17328kb

input:

500000
1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -...

output:

31249875000

result:

ok 1 number(s): "31249875000"

Test #22:

score: 0
Accepted
time: 16ms
memory: 17244kb

input:

499999
1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -...

output:

31249875000

result:

ok 1 number(s): "31249875000"

Test #23:

score: 0
Accepted
time: 23ms
memory: 17252kb

input:

499997
-1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...

output:

31249375003

result:

ok 1 number(s): "31249375003"

Test #24:

score: 0
Accepted
time: 21ms
memory: 17328kb

input:

500000
1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -...

output:

-1

result:

ok 1 number(s): "-1"

Subtask #3:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #25:

score: 0
Wrong Answer
time: 1ms
memory: 7680kb

input:

10
0 1 0 0 1 1 -1 0 1 -1

output:

3

result:

wrong answer 1st numbers differ - expected: '9', found: '3'

Subtask #4:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #44:

score: 0
Wrong Answer
time: 30ms
memory: 17328kb

input:

500000
1 1 -1 0 0 -1 1 -1 0 0 1 1 -1 -1 -1 1 -1 1 0 0 -1 1 1 0 0 0 0 0 1 0 -1 0 -1 1 1 0 0 -1 1 0 0 0 0 0 -1 0 0 -1 1 1 0 0 1 0 0 1 -1 0 1 0 0 0 0 -1 1 0 1 0 -1 0 -1 1 1 0 -1 0 0 0 0 0 0 1 -1 1 -1 1 0 1 -1 0 1 -1 0 -1 -1 1 1 0 1 0 -1 0 0 0 -1 0 -1 0 0 1 -1 1 0 0 1 0 1 0 1 0 0 -1 0 1 1 -1 -1 0 0 -1 -...

output:

-1

result:

wrong answer 1st numbers differ - expected: '15602272809', found: '-1'

Subtask #5:

score: 0
Wrong Answer

Test #60:

score: 0
Wrong Answer
time: 1ms
memory: 7756kb

input:

10
3 10 5 -9 7 2 -6 1 8 0

output:

0

result:

wrong answer 1st numbers differ - expected: '-1', found: '0'

Subtask #6:

score: 0
Skipped

Dependency #5:

0%

Subtask #7:

score: 0
Skipped

Dependency #3:

0%

Subtask #8:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%