CSES - KILO 2017 5/5 - Results
Submission details
Task:Zero Game
Sender:Ke Bi
Submission time:2017-10-03 18:27:50 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.04 sdetails
#2ACCEPTED0.06 sdetails
#3ACCEPTED0.06 sdetails
#4ACCEPTED0.20 sdetails
#5ACCEPTED0.21 sdetails
#6ACCEPTED0.23 sdetails
#7ACCEPTED0.23 sdetails
#8ACCEPTED0.23 sdetails
#9ACCEPTED0.22 sdetails
#10ACCEPTED0.23 sdetails
#11ACCEPTED0.22 sdetails
#12ACCEPTED0.22 sdetails
#13ACCEPTED0.22 sdetails
#14ACCEPTED0.24 sdetails
#15ACCEPTED0.19 sdetails
#16ACCEPTED0.23 sdetails
#17ACCEPTED0.23 sdetails
#18ACCEPTED0.21 sdetails
#19ACCEPTED0.19 sdetails
#20ACCEPTED0.18 sdetails
#21ACCEPTED0.19 sdetails
#22ACCEPTED0.19 sdetails
#23ACCEPTED0.17 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:8:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", s);
                ^
input/code.cpp:26:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &tt);
                  ^
input/code.cpp:28:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &d);
                  ^

Code

#include <bits/stdc++.h>
using namespace std;
char s[1000020];
int a[1000020], c, n;
int b[1000020];
int q[1000020], l, r, d;
int main() {
	scanf("%s", s);
	int n = strlen(s);
	s[n++] = '1';
	int zero = 0, szero = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == '0') {
			zero++;
			szero++;
		} else {
			a[c++] = zero;
			zero = 0;
		}
	}
	for (int i = 0; i < c; i++) {
		a[i]--;
		b[i + 1] = b[i] + a[i];
	}
	int tt;
	scanf("%d", &tt);
	for (int _ = 0; _ < tt; _++) {
		scanf("%d", &d);
		l = r = 0;
		int ans = min(d, szero);
		for (int i = 0; i <= c; i++) {
			while (l < r) {
				if (b[i] < b[q[r - 1]]) {
					r--;
				} else {
					break;
				}
			}
			q[r++] = i;
			if (i - q[l] > d + 1) {
				l++;
			}
			ans = max(ans, b[i] - b[q[l]] + d + 1);
		}
		ans = min(ans, szero);
		printf("%d\n", ans);
	}
	return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
0000110000111110
5
1
2
3
...

correct output
5
8
9
9
9

user output
5
8
9
9
9

Test 2

Verdict: ACCEPTED

input
0
3
1
2
1000000

correct output
1
1
1

user output
1
1
1

Test 3

Verdict: ACCEPTED

input
1
3
1
2
1000000

correct output
0
0
0

user output
0
0
0

Test 4

Verdict: ACCEPTED

input
101010000100110111100010011111...

correct output
27508
3952
38438
41043
45967
...

user output
27508
3952
38438
41043
45967
...

Test 5

Verdict: ACCEPTED

input
010011011010011111000010000101...

correct output
2539
44377
14738
16082
24442
...

user output
2539
44377
14738
16082
24442
...

Test 6

Verdict: ACCEPTED

input
100111100001001111101011110011...

correct output
32545
50046
1718
28159
50078
...

user output
32545
50046
1718
28159
50078
...

Test 7

Verdict: ACCEPTED

input
100010110100001011000100010110...

correct output
5417
10857
39391
7219
16158
...

user output
5417
10857
39391
7219
16158
...

Test 8

Verdict: ACCEPTED

input
101101110000000011101010001001...

correct output
28572
3982
4294
42653
15568
...

user output
28572
3982
4294
42653
15568
...

Test 9

Verdict: ACCEPTED

input
100010010011011100110101100110...

correct output
39423
42215
20939
22244
6606
...

user output
39423
42215
20939
22244
6606
...

Test 10

Verdict: ACCEPTED

input
101011100110001100000001001011...

correct output
49496
38784
33144
32488
31351
...

user output
49496
38784
33144
32488
31351
...

Test 11

Verdict: ACCEPTED

input
001111010111101100101001011100...

correct output
6917
21861
18615
25072
18596
...

user output
6917
21861
18615
25072
18596
...

Test 12

Verdict: ACCEPTED

input
010100101011111011110010100011...

correct output
43850
8690
13226
41153
42409
...

user output
43850
8690
13226
41153
42409
...

Test 13

Verdict: ACCEPTED

input
010001110100010111010000110011...

correct output
39994
40744
20457
16265
47047
...

user output
39994
40744
20457
16265
47047
...

Test 14

Verdict: ACCEPTED

input
111111100111110001110100000010...

correct output
459798
278541
204171
233150
5113
...

user output
459798
278541
204171
233150
5113
...

Test 15

Verdict: ACCEPTED

input
000010001111100111111000010011...

correct output
446184
279158
311949
469694
260672
...

user output
446184
279158
311949
469694
260672
...

Test 16

Verdict: ACCEPTED

input
000001011010011011010000001111...

correct output
85605
392194
287645
324684
389995
...

user output
85605
392194
287645
324684
389995
...

Test 17

Verdict: ACCEPTED

input
100111001111000111001010110100...

correct output
415271
228907
279960
376429
366346
...

user output
415271
228907
279960
376429
366346
...

Test 18

Verdict: ACCEPTED

input
011101101010000110000010011001...

correct output
473458
106311
430917
402707
240473
...

user output
473458
106311
430917
402707
240473
...

Test 19

Verdict: ACCEPTED

input
101001101011100000001000111000...

correct output
1776
2430
1210
1495
2085
...

user output
1776
2430
1210
1495
2085
...

Test 20

Verdict: ACCEPTED

input
011110000111000101000001111000...

correct output
1572
2349
3106
1565
2248
...

user output
1572
2349
3106
1565
2248
...

Test 21

Verdict: ACCEPTED

input
110011111011001101011001000000...

correct output
410
2693
504
1777
1380
...

user output
410
2693
504
1777
1380
...

Test 22

Verdict: ACCEPTED

input
000110111101111111110001110000...

correct output
2679
2282
564
1755
845
...

user output
2679
2282
564
1755
845
...

Test 23

Verdict: ACCEPTED

input
111011100111000001100000001100...

correct output
820
787
2553
911
3095
...

user output
820
787
2553
911
3095
...