QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#745535#9565. Birthday Gifttest_algthWA 9ms7264kbC++201.7kb2024-11-14 10:28:492024-11-14 10:28:51

Judging History

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

  • [2024-11-14 10:28:51]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:7264kb
  • [2024-11-14 10:28:49]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
typedef pair <int, int> pii;

inline int read() {
	int x = 0, f = 0;
	char c = getchar();
	while (!isdigit(c)) {if (c == '-') f = 1; c = getchar();}
	while (isdigit(c)) x = (x << 1) + (x << 3) + (c & 15), c = getchar();
	return f? -x : x;
}

const int MAXN = 2e5;
char str[MAXN + 10];
pii dp[MAXN + 10][2];

inline int chk(pii &res) {
	return res.fi != -1 && res.se != -1;
}
void upd(int i, int o) {
	if (dp[i - 1][o ^ 1] != mkp(-1, -1))
		dp[i][o] = mkp(dp[i - 1][o ^ 1].fi + 1, dp[i - 1][o ^ 1].se + 1);
	if (dp[i - 1][o] != mkp(0, 0) && dp[i - 1][o] != mkp(-1, -1))
		dp[i][o ^ 1] = mkp(max(dp[i - 1][o].fi - 1, 0), dp[i - 1][o].se - 1);
}

void fk(int i, int o) {
	if (dp[i - 1][o ^ 1] == mkp(-1, -1)) return;
	if (dp[i - 1][o ^ 1] != mkp(0, 0))
		dp[i][o] = mkp(max(dp[i - 1][o ^ 1].fi - 1, 0), dp[i - 1][o ^ 1].se + 1);
	else dp[i][o] = mkp(1, 1);
}

int main() {
//	freopen ("std.in", "r", stdin);
//	freopen ("std.out", "w", stdout);
	int T = read();
	while (T--) {
		scanf("%s", str + 1);
		int n =strlen(str + 1);
		for (int i = 1; i <= n; ++i) {
			dp[i][0] = dp[i][1] = mkp(-1, -1);
			if (str[i] == '0')
				upd(i, 0);
			if (str[i] == '1')
				upd(i, 1);
			if (str[i] == '2') {
				fk(i, 0);
				fk(i, 1);
			}
			if (dp[i][0].fi == 0) {
				dp[i][1].fi = 0;
				dp[i][1].se = max(dp[i][1].se, 0);
			}
			if (dp[i][1].fi == 0) {
				dp[i][0].fi = 0;
				dp[i][0].se = max(dp[i][0].se, 0);
			}
		}
		int ans = n;
		if (dp[n][0].fi != -1) ans = min(ans, dp[n][0].fi);
		if (dp[n][1].fi != -1) ans = min(ans, dp[n][1].fi);
		printf("%d\n", ans);
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3896kb

input:

5
0110101
01020102
0000021111
1012121010
0100202010

output:

3
4
0
6
0

result:

ok 5 number(s): "3 4 0 6 0"

Test #2:

score: 0
Accepted
time: 8ms
memory: 3904kb

input:

50000
1010110101
1010101010
0101010101
0101010010
0101010010
1010101010
0101001010
1010010010
0100101010
1010101001
1010100101
0101010100
0100101011
0101101010
1011010110
1011010101
1010010101
1010010010
0101010101
0010101010
0101011010
0100101010
1010101010
1010010101
1010101101
1101010101
10100101...

output:

0
10
10
4
4
10
0
4
4
6
2
8
2
2
0
4
2
4
10
8
2
4
10
2
4
8
2
8
8
4
8
4
4
6
4
4
4
6
10
10
2
2
0
10
8
10
0
10
10
10
4
10
8
10
0
8
4
0
8
2
8
0
6
2
8
10
4
10
10
2
10
2
10
8
6
4
2
8
8
0
8
10
8
10
8
10
2
6
10
4
10
8
10
4
10
6
10
10
10
6
6
6
4
10
10
10
2
2
8
10
6
10
10
8
4
10
6
10
2
2
8
2
10
4
6
0
10
4
6
2
1...

result:

ok 50000 numbers

Test #3:

score: 0
Accepted
time: 2ms
memory: 3904kb

input:

5000
1010101010101010101110101010101010100101010101010101010110101010101010101010101010101010101010101010
0101010101010101010101010101101010101010101010101010101010101010101010101010100101010101010110101010
010101010101010101010101010101010101010101010101010101010101010101010100101010101010101010101...

output:

58
16
44
26
2
30
62
14
16
68
44
78
58
54
52
4
22
60
12
60
12
82
64
68
44
4
34
12
82
16
64
12
14
46
48
12
94
12
82
50
30
40
8
88
62
20
2
46
86
36
16
20
18
74
66
36
80
98
26
0
30
72
40
70
28
80
52
18
94
62
32
26
18
92
44
80
48
4
28
32
34
50
80
54
80
32
62
62
76
70
78
16
16
2
2
58
46
18
56
26
36
56
76
...

result:

ok 5000 numbers

Test #4:

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

input:

500
01010101010101010101010101010101010101010101010101010101010101010101001010101010101010101010110101010101010101010101010101010101010101010100101101010101010010101010101010101010101010101010101010101010101010101010101010101101010101010101010101010101010101010101010101010101001010101010101001010100...

output:

28
12
76
174
24
124
142
142
142
194
216
70
12
176
18
310
16
188
38
42
164
110
162
4
12
24
2
96
206
4
238
64
64
28
50
54
278
182
122
86
4
76
44
146
118
122
276
268
148
32
78
90
202
40
20
240
128
116
228
282
36
178
160
88
2
20
114
70
248
68
54
18
18
210
46
126
26
52
0
298
6
16
160
32
92
56
106
126
246...

result:

ok 500 numbers

Test #5:

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

input:

50
101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...

output:

836
3994
352
3984
1826
568
2088
4076
1750
1258
532
3036
1718
1106
1002
478
1838
2030
422
4210
828
2088
2930
4044
1406
2388
3586
2018
1976
1026
5092
4154
3478
1018
1998
4014
718
2852
6070
2518
6380
4826
170
1876
1096
3914
1692
574
4612
802

result:

ok 50 numbers

Test #6:

score: 0
Accepted
time: 4ms
memory: 4052kb

input:

50
010101010101101110100100101010101100010100110100101001011010101000100101001010100101101010001011010110010101010101010101011011000010001001010101010110101010111010011010101010100101001010101010101100101010101010100101010101010100011101110101010011010101011010110100110101010010010101101101011001010...

output:

152
84
110
60
218
124
190
198
76
98
202
234
126
160
236
134
44
324
176
136
178
156
46
220
8
106
18
136
346
74
30
104
310
264
160
224
198
218
314
166
166
54
82
246
242
62
164
26
336
124

result:

ok 50 numbers

Test #7:

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

input:

2
0101010101010101010101010101010010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010...

output:

6648
174

result:

ok 2 number(s): "6648 174"

Test #8:

score: 0
Accepted
time: 6ms
memory: 3904kb

input:

50000
0100202010
0101221101
0120120101
1210102101
1210101020
1020210101
0200101020
1010210120
0121012010
0212101010
0201010120
1101010221
0012101020
1110101221
1010121201
1202010101
0210012101
0210010102
2101210101
0101002201
0102101210
1020101201
1201002101
0101022010
0201101012
1210010210
20120101...

output:

0
4
2
0
6
0
2
0
0
4
4
4
4
2
2
4
2
2
6
4
0
2
2
0
0
0
2
2
0
4
2
0
0
4
2
4
6
6
4
0
2
4
2
2
0
4
6
6
0
2
4
0
4
4
4
2
0
4
2
0
6
4
6
0
0
4
4
0
6
4
0
0
2
0
6
6
4
0
6
0
0
0
6
2
2
4
2
6
2
0
6
6
2
0
6
2
0
6
4
6
2
0
4
2
0
4
0
6
4
2
6
4
6
2
0
2
4
0
0
0
0
0
2
0
0
0
2
2
4
4
0
4
0
4
4
0
0
4
4
4
0
0
4
2
2
0
2
2
4
2
...

result:

ok 50000 numbers

Test #9:

score: 0
Accepted
time: 5ms
memory: 3952kb

input:

5000
1010101012010101010112010120120102010110100101012101010100101010210101010201010100121010101201010110
0101010101102102010101010101010101010101012012210101010120101010101010120201010102010101010100012011
010201010101212010110201201010101210101010101010101010101101010110121010100101010101021010101...

output:

12
38
12
52
10
0
6
0
34
26
14
0
10
0
14
22
6
30
20
0
2
0
6
0
0
0
16
0
4
0
0
36
4
30
46
14
14
0
26
18
14
30
30
6
0
10
0
28
0
16
26
12
2
28
40
2
2
26
44
0
2
14
18
20
0
8
0
0
40
8
4
4
46
52
2
20
6
6
16
38
38
26
12
0
26
10
0
0
10
36
8
16
16
16
0
0
12
28
0
30
14
22
0
38
22
20
14
26
26
10
30
34
8
20
6
26
...

result:

ok 5000 numbers

Test #10:

score: 0
Accepted
time: 6ms
memory: 3952kb

input:

5000
1210201012021010102101010101010101010102011010220101021010122112010101201012211201001220101020120101
1020102101011012200110101012021001010110101012010221010100222010201010121101010101201010201012221200
101010210110120101010210222101002102102100201012110101201010101101010220101010221001201010201...

output:

0
0
0
0
0
0
0
20
0
0
0
0
0
0
20
0
0
0
2
0
2
4
6
0
0
0
0
0
0
0
16
16
0
0
0
0
0
0
0
0
0
0
12
0
0
0
0
0
0
0
0
0
22
12
0
12
12
10
0
0
0
0
0
0
0
0
0
10
6
0
0
0
18
6
0
0
16
0
0
0
0
0
0
0
2
0
22
0
0
2
0
0
0
6
0
4
0
24
0
6
6
2
0
0
0
0
0
0
12
0
0
0
0
0
26
0
0
0
0
0
0
0
0
4
0
0
26
0
0
0
12
0
0
0
4
0
0
4
12
0
...

result:

ok 5000 numbers

Test #11:

score: 0
Accepted
time: 4ms
memory: 5956kb

input:

500
01010101120101010101010101010101010101210101010101010101010101010101010101010101010101010101010101010102010101010101010101010101021010101010101010101201201010101010102201010110101101010120101010101010101010101010120101020101010101010102101010101010101210101012010101020101011010101010101010101010...

output:

138
178
0
0
30
0
0
68
56
174
0
0
38
72
46
0
0
250
266
58
140
122
124
24
98
0
0
0
126
106
34
64
6
132
0
20
90
370
86
134
12
308
106
158
8
98
128
0
30
52
100
218
222
0
0
100
36
38
34
50
110
0
114
42
148
92
94
138
142
0
90
0
0
76
176
0
148
0
250
92
114
102
26
0
0
156
52
0
104
0
32
18
46
84
0
8
64
0
72
...

result:

ok 500 numbers

Test #12:

score: 0
Accepted
time: 4ms
memory: 3784kb

input:

500
10101010101010101010101010101001010101001010101010101010101010101010101001010101010101010101010101000101010101010101010101010100101010010010101001010101010100101010101010110101011101010101010101010101010101010101010101011010101010101010101010120101010101010201010101021010101010101010101010101010...

output:

16
30
136
200
304
56
20
88
10
36
64
158
92
196
30
298
314
248
0
158
144
310
166
120
10
0
76
232
20
2
128
100
126
154
58
102
116
16
214
62
212
208
44
14
186
22
0
52
118
28
94
140
130
58
94
214
148
34
56
192
62
82
28
100
58
132
36
202
6
92
0
120
192
166
144
52
76
172
68
254
14
58
274
94
226
162
42
44
...

result:

ok 500 numbers

Test #13:

score: 0
Accepted
time: 5ms
memory: 3904kb

input:

500
10101010202010101010120201012010101010101010101010101201201010101010101010102210101010122121210101010210210101010101012010101010102201210101010102220102120101010101010122101210120121010120101010101020101201020201020101202201010102220101010101010101101012010101202012210101210101010101010101210101...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
20
0
0
0
0
0
0...

result:

ok 500 numbers

Test #14:

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

input:

50
101010121010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...

output:

3814
3524
2852
1062
1438
868
2466
3168
2894
2584
114
454
4056
1966
2978
2354
2348
3160
3824
4726
1080
168
894
810
3150
494
1298
1384
6540
1722
2342
4232
1810
2840
1122
1684
2742
1272
1814
188
2216
2742
2336
1648
388
1194
2286
3708
562
1784

result:

ok 50 numbers

Test #15:

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

input:

50
101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101001010101010101010101010101010101010101001010210101010010101010101201010101010101010101010101010101010101010101010101010101010101010101010...

output:

1912
458
0
592
0
1324
1472
518
6
750
0
1334
126
102
462
542
0
584
612
378
508
166
34
116
1252
508
526
32
74
208
136
70
636
1324
228
74
1804
0
666
272
284
232
322
634
862
896
104
292
480
100

result:

ok 50 numbers

Test #16:

score: 0
Accepted
time: 6ms
memory: 5928kb

input:

50
010201010101010101010101220102120121210101020101010210101010201210201010101220101212212010121010210101010101022010101010101010101012101010121221010102101010101022010101010101010101012021010102101202101012010220201010220101010101012101010101010120202021010101012010201021021010220101210101021202201...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 50 numbers

Test #17:

score: 0
Accepted
time: 4ms
memory: 4120kb

input:

50
010101010101010101010101010111010101011012101010101010101011010101010101010101010101011010101101010101010101010101010101101010101010121010201010101010221010101020101010101012101010110101010101121010101010010101010011010101010101101010101101010100101010102210212010101010101010101010010101010101010...

output:

184
306
0
0
0
0
422
0
396
0
0
0
2
0
172
0
0
0
0
0
0
0
0
108
0
50
182
0
0
48
64
410
360
0
0
42
0
806
330
260
0
96
0
0
132
0
0
404
100
0

result:

ok 50 numbers

Test #18:

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

input:

2
1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010...

output:

12306
14212

result:

ok 2 number(s): "12306 14212"

Test #19:

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

input:

2
0101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010102010101010101010101010101010101010101010101010101010101010101010101...

output:

13352
522

result:

ok 2 number(s): "13352 522"

Test #20:

score: 0
Accepted
time: 5ms
memory: 7264kb

input:

2
1010101010101012101012122021201010101010210101010101010101202201010101010120102210220101010101010102101010101010101012101210101020101010220210101010101010101020101210101012010101201010201021010101012122121012010121012021010101201012010120101221010101201010101210101021021021010101010101012012010210...

output:

0
0

result:

ok 2 number(s): "0 0"

Test #21:

score: 0
Accepted
time: 5ms
memory: 7204kb

input:

2
0101010121012101012101010101010121010101010101010101010101010101010101010210120101010102101010220101210210101010101010101010101010210101021010101020101010101021210101010102101010101010101010101010101010101010210101010101010101010101010102101010101010101010101010101010120101220101010101010101010101...

output:

0
0

result:

ok 2 number(s): "0 0"

Test #22:

score: 0
Accepted
time: 7ms
memory: 3888kb

input:

50000
010101101
010100101
010101010
101010010
011010110
010101010
011010101
010100100
001010101
001010101
101010011
001010101
101010101
101010110
010101010
101010101
010101010
010110101
010100101
101010101
101010101
101010101
101010100
100101001
100101101
010101101
010100101
101010101
100100101
0010...

output:

3
1
9
3
1
9
5
3
7
7
5
7
9
5
9
9
9
1
1
9
9
9
7
1
1
3
1
9
3
3
7
9
5
7
5
9
9
7
5
5
3
9
9
1
5
9
1
5
7
1
5
7
9
9
3
7
5
7
3
7
3
9
9
5
3
3
1
9
5
5
1
3
5
3
9
3
7
3
9
9
5
7
7
3
1
9
9
9
7
5
9
9
9
9
9
5
5
3
7
7
9
9
3
9
9
1
1
9
5
7
3
5
1
5
5
9
9
7
1
3
9
7
1
9
9
5
9
7
5
7
7
7
3
9
3
1
5
9
5
1
5
1
9
5
3
9
9
3
9
3
...

result:

ok 50000 numbers

Test #23:

score: 0
Accepted
time: 4ms
memory: 3880kb

input:

5000
010101010101010101010101010101010101010101011010101010101010101010101010100101010100101010100101010
101010101010101010101010101010101010101010101010101010110101010101010101010101010110101010101010101
10100101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010...

output:

21
45
91
35
31
71
95
41
65
19
87
99
33
73
27
33
7
11
97
53
55
43
15
87
35
99
97
9
51
37
83
3
53
89
81
21
49
21
91
3
49
13
37
75
45
89
57
1
95
95
19
71
69
13
23
25
39
85
51
99
43
11
73
99
7
9
37
7
55
9
25
61
11
57
81
29
53
79
47
49
41
31
21
65
43
67
9
5
21
41
87
59
19
67
79
95
63
83
75
65
89
27
39
39...

result:

ok 5000 numbers

Test #24:

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

input:

500
10101010101010101010010101010101010101010101010010101010101011010111010101010101010110101010101010101010101010101010110101010101010101010100101010101010101010101010101010101010101010100110110101010101010101001010101010101101010101010101010101010010101011010101010101010101010101010101001010110101...

output:

99
65
129
185
15
15
99
113
11
89
119
293
65
105
215
29
127
195
89
119
183
95
87
229
7
219
249
37
41
59
143
61
115
209
51
27
5
81
71
239
25
179
87
131
205
11
215
9
87
37
219
21
113
47
39
49
35
129
311
93
215
215
99
33
117
225
97
179
107
107
103
25
99
149
121
25
177
87
29
27
5
109
5
99
95
179
83
99
19...

result:

ok 500 numbers

Test #25:

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

input:

50
101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...

output:

955
2477
961
1029
249
1137
845
65
915
559
1593
457
1023
3465
3785
2839
1375
593
3927
3349
3273
1283
1563
3637
873
313
439
5929
4059
3567
4759
4793
535
1611
5251
1287
937
2057
483
4635
1193
4483
207
1375
493
2637
537
5
409
743

result:

ok 50 numbers

Test #26:

score: 0
Accepted
time: 4ms
memory: 3992kb

input:

50
011010010110101011100101010101001011010101001010101010110010101010101010110101010101010000101010101010010110110001001010100101101010101101010101110101010110101010101010100100101010110101010100101010101101001011001010101010010100010010010101010100010101010101010101010101010101011010101010010101010...

output:

193
157
463
51
261
83
31
153
123
3
65
271
435
147
83
325
39
47
315
73
309
177
71
239
111
243
301
49
43
119
91
115
251
235
121
89
405
431
309
139
177
41
39
17
121
233
161
3
57
129

result:

ok 50 numbers

Test #27:

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

input:

2
0101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010110101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010...

output:

17045
1847

result:

ok 2 number(s): "17045 1847"

Test #28:

score: -100
Wrong Answer
time: 9ms
memory: 3892kb

input:

50000
010100122
110201201
101021012
202001001
102010102
012010102
101211020
201010102
012101012
010212010
211201010
001020120
121101012
210101210
012102101
102020101
101220101
121012010
101201210
011010220
102101020
010201210
101020120
210101021
101010220
012010102
011012012
010221010
202001011
2101...

output:

1
0
0
0
5
1
0
5
5
3
3
1
1
5
0
5
5
0
0
0
1
5
3
3
3
1
0
5
0
3
3
1
0
0
1
0
1
1
5
3
1
1
5
0
0
1
3
5
1
3
1
1
5
5
0
3
0
0
5
0
3
3
0
0
3
3
1
1
3
3
5
3
5
5
1
1
1
5
0
0
5
0
0
3
3
5
1
1
1
3
5
3
5
5
0
5
0
1
3
0
0
0
3
1
0
3
5
5
5
0
0
5
3
3
0
5
5
3
1
5
5
1
5
1
1
0
1
5
5
3
0
5
0
3
3
3
5
5
5
0
5
3
0
1
0
3
5
3
5
0
...

result:

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