Task: | Zero Game |
Sender: | Ke Bi |
Submission time: | 2017-10-03 18:27:50 +0300 |
Language: | C++ |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.04 s | details |
#2 | ACCEPTED | 0.06 s | details |
#3 | ACCEPTED | 0.06 s | details |
#4 | ACCEPTED | 0.20 s | details |
#5 | ACCEPTED | 0.21 s | details |
#6 | ACCEPTED | 0.23 s | details |
#7 | ACCEPTED | 0.23 s | details |
#8 | ACCEPTED | 0.23 s | details |
#9 | ACCEPTED | 0.22 s | details |
#10 | ACCEPTED | 0.23 s | details |
#11 | ACCEPTED | 0.22 s | details |
#12 | ACCEPTED | 0.22 s | details |
#13 | ACCEPTED | 0.22 s | details |
#14 | ACCEPTED | 0.24 s | details |
#15 | ACCEPTED | 0.19 s | details |
#16 | ACCEPTED | 0.23 s | details |
#17 | ACCEPTED | 0.23 s | details |
#18 | ACCEPTED | 0.21 s | details |
#19 | ACCEPTED | 0.19 s | details |
#20 | ACCEPTED | 0.18 s | details |
#21 | ACCEPTED | 0.19 s | details |
#22 | ACCEPTED | 0.19 s | details |
#23 | ACCEPTED | 0.17 s | details |
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 ... |