QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#95888#6299. Binary Stringpsc233RE 806ms85260kbC++142.1kb2023-04-12 12:17:302023-04-12 12:17:33

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-12 12:17:33]
  • 评测
  • 测评结果:RE
  • 用时:806ms
  • 内存:85260kb
  • [2023-04-12 12:17:30]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
char s[N];
int nxt[N<<1],f[N],q[N<<1];
int T,n;
int kmp(){
	for (int i=n;i<n*2;i++) s[i]=s[i-n];
	nxt[0]=0;
	for (int i=1;i<n*2;i++){
		nxt[i]=nxt[i-1];
		while (nxt[i]&&s[nxt[i]]!=s[i]) nxt[i]=nxt[nxt[i]-1];
		if (s[nxt[i]]==s[i]) nxt[i]++;
	}
	int s=n*2-nxt[2*n-1];
	return s;
}
int main(){
	scanf("%d",&T);
	while (T--){
		scanf("%s",s);
		n=strlen(s);
		if (n==1){
			puts("1"); continue;
		}
		int sum=0;
		for (int i=0;i<n;i++) if (s[i]=='0') sum++;
		if (sum*2>n){
			for (int i=0;i<n;i++) if (s[i]=='0') s[i]='1'; else s[i]='0';
			for (int i=0;i<n-1-i;i++) swap(s[i],s[n-1-i]);
		}
		bool p=0;
		for (int i=0;i<n;i++) if (s[i]=='0'&&s[(i+1)%n]=='0') p=1; 
		int ans=0;
		if (p){
			ans++;
			int tag=0;
			for (int i=0;i<n-tag;i++) if (s[i]=='0'&&s[(i+1)%n]=='1'){
//				cout << i << endl;
				if (i==0) tag=1;
				swap(s[i],s[(i+1)%n]); i++;
			}
		}
		/*
		1111100101000111
		1111101010001011
		1111110100010101
		1111111000101010
		0111111001010101
		1011111010101010//循环开始
		*/
//		cout << s << endl;
		for (int i=n;i<n*2;i++) s[i]=s[i-n];
		f[0]=(s[0]=='1'?1:-1);
		for (int i=1;i<n*2;i++) f[i]=f[i-1]+(s[i]=='1'?1:-1);
		int cnt=0,ws=0;
		vector<int>w;
		for (int i=n*2-1;i>=0;i--){
			q[++cnt]=i;
			while (cnt>1&&f[q[cnt]]<=f[q[cnt-1]]) cnt--,q[cnt]=q[cnt+1];
			if (i<n&&s[i+1]=='1'){
				if (cnt==1) w.push_back((i+1)%n);
				else {
				ws=max(ws,(q[cnt-1]-q[cnt]-1)/2);
//				cout << q[cnt] << ' ' << q[cnt-1] << endl;
				}
			}
		}
//		cout << ws << endl;
		ans+=ws;
		if (!(int)w.size()) ans+=2;
		else{
		for (int i=0;i<n;i++) s[i]='?';
		for (int i=0;i<w.size();i++){
			s[(w[i]+ws)%n]='1';
		}
		int j=0;
		for (int i=0;i<n;i++) if (s[i]=='1'){
			int t=0;
			for (int k=i-1;k>=j;k--,t^=1) s[k]=(t?'1':'0');
			j=i+1;
		}
		int t=0;
		for (int i=j;i<n;i++,t^=1) s[i]=(t?'1':'0');
		ans+=kmp();
		}
		printf("%d\n",ans);
	}
}
/*
	01101011010
	10110101100
*/
/*
	10100101001
	11001010010
	01010100101
	10101001010
	01010010101
	
*/

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3648kb

input:

3
1
001001
0001111

output:

1
3
9

result:

ok 3 number(s): "1 3 9"

Test #2:

score: 0
Accepted
time: 237ms
memory: 3728kb

input:

262144
000000000000000000
100000000000000000
010000000000000000
110000000000000000
001000000000000000
101000000000000000
011000000000000000
111000000000000000
000100000000000000
100100000000000000
010100000000000000
110100000000000000
001100000000000000
101100000000000000
011100000000000000
11110000...

output:

1
18
18
19
18
18
19
20
18
18
18
20
19
19
20
21
18
18
18
19
18
18
20
21
19
19
19
21
20
20
21
22
18
18
18
19
18
18
19
21
18
18
18
21
20
20
21
22
19
19
19
19
19
19
21
22
20
20
20
22
21
21
22
23
18
18
18
19
18
18
19
20
18
18
18
20
19
19
21
22
18
18
18
19
18
18
21
22
20
20
20
22
21
21
22
23
19
19
19
19
1...

result:

ok 262144 numbers

Test #3:

score: 0
Accepted
time: 496ms
memory: 3688kb

input:

524288
0000000000000000000
1000000000000000000
0100000000000000000
1100000000000000000
0010000000000000000
1010000000000000000
0110000000000000000
1110000000000000000
0001000000000000000
1001000000000000000
0101000000000000000
1101000000000000000
0011000000000000000
1011000000000000000
0111000000000...

output:

1
19
19
20
19
19
20
21
19
19
19
21
20
20
21
22
19
19
19
20
19
19
21
22
20
20
20
22
21
21
22
23
19
19
19
20
19
19
20
22
19
19
19
22
21
21
22
23
20
20
20
20
20
20
22
23
21
21
21
23
22
22
23
24
19
19
19
20
19
19
20
21
19
19
19
21
20
20
22
23
19
19
19
20
19
19
22
23
21
21
21
23
22
22
23
24
20
20
20
20
2...

result:

ok 524288 numbers

Test #4:

score: 0
Accepted
time: 806ms
memory: 3656kb

input:

952358
0011101111
101010101101
101111111010100
0101011000110001100
0101111101110
010
100100000111011
011010110110011
1010111
1
1111101010
11111011001111110
0101101101011
001
1100111100
100011
10
10
0001
011100
1100010
111111101010010
01001111110011011
01100
1010
10101111
01000111100011111110
10101
0...

output:

11
12
18
20
14
3
21
16
7
1
10
18
13
3
11
4
2
2
4
4
8
18
19
6
2
8
24
5
1
1
5
25
1
14
1
15
20
3
7
24
12
10
20
21
23
1
22
18
22
5
1
6
18
12
1
4
5
12
13
12
21
1
5
12
21
8
1
8
18
4
1
12
13
6
3
3
16
6
8
1
1
17
1
1
1
6
6
4
4
10
7
5
4
5
24
6
11
4
8
15
3
9
9
19
5
16
11
5
6
9
17
1
25
14
6
1
4
20
1
4
20
14
14
...

result:

ok 952358 numbers

Test #5:

score: 0
Accepted
time: 790ms
memory: 3728kb

input:

645561
001000111110000
01001111000
01011010
110000110111111111
0110100010000100
0
010011
010011111
00000111100001101110101100001
10111111000
100
1101100000001010110110101
1001111101
000100
101
1110101100011111101001111
000111100111100
1111001101011000000
100101001001001010111011011111
10111001100111...

output:

19
14
4
21
18
1
4
11
37
13
3
34
11
6
3
29
21
27
38
24
13
22
26
39
26
31
10
22
1
17
34
40
18
9
29
31
11
3
28
15
20
27
29
16
2
23
18
31
5
14
33
18
1
1
18
7
36
17
34
1
18
6
16
20
19
3
18
36
21
23
21
4
30
12
4
35
16
18
35
2
25
20
31
17
26
24
3
24
6
26
25
17
13
7
24
27
25
18
22
10
20
4
6
23
17
30
16
22
3...

result:

ok 645561 numbers

Test #6:

score: 0
Accepted
time: 694ms
memory: 3652kb

input:

488486
01101101
011000000100011010101011010
0100101110001011
00111110011110011010001101010000
11010010000010011111011010000010001
01001111001000010110
10110010011010100101010101111
10100000000001
1000010010
0
1111
10001010011011001111100101010
01010111100001011111011110101110101
11100
10101010001101...

output:

8
36
4
17
43
24
33
16
10
1
1
39
38
6
40
30
51
17
41
1
1
12
34
49
44
38
18
47
39
14
35
32
14
36
31
37
23
42
3
10
18
15
21
14
33
11
17
5
18
45
39
31
38
52
27
22
38
15
16
26
30
3
2
3
29
1
41
40
14
17
24
50
21
34
11
31
9
31
18
32
21
43
1
42
39
10
36
27
27
29
15
13
1
24
46
22
21
13
29
13
14
45
47
45
43
1...

result:

ok 488486 numbers

Test #7:

score: 0
Accepted
time: 667ms
memory: 3736kb

input:

392510
01
00110011011000101011100
0100001010100011111011100011101011111100001110
1011001
00100110000011010
1101110
000100011000001111111100101011110111010111110
0111110000001010111110100011
0100111110000000111101110011011100100
100110000111101101101011011110001101111
111
0000001101011
11101100
10000...

output:

2
26
62
8
19
7
59
34
54
44
1
17
9
43
37
5
1
17
10
30
52
32
11
36
16
37
45
31
12
44
31
45
43
16
11
10
51
41
48
31
22
1
13
1
33
27
25
35
2
5
15
27
6
49
33
3
33
38
52
60
48
28
35
31
25
5
1
44
67
31
36
6
24
31
1
35
56
44
38
36
15
14
49
61
57
61
44
22
38
27
11
51
53
13
30
34
4
56
51
18
2
29
42
51
2
15
9
...

result:

ok 392510 numbers

Test #8:

score: 0
Accepted
time: 578ms
memory: 3736kb

input:

197451
00010111010000100100110001010100100100101001111001000101101001010111100010110101001000001
0000011
11010001011010010010001000011111001110110100111110000010101100110000001100111
0110101110000001001010100
10100010
0110100111
010101000100011001110000000110000000011101010011101
0000110110101011001...

output:

98
8
112
30
8
12
63
96
73
123
10
106
5
106
28
24
101
44
85
109
69
29
104
76
106
111
126
8
106
89
44
36
9
56
9
111
28
37
94
6
102
2
116
19
5
50
32
17
97
114
127
12
26
9
90
133
109
9
66
27
95
1
59
59
93
40
139
84
51
33
101
127
27
1
86
12
95
41
90
134
87
24
109
57
11
85
60
50
4
52
133
66
58
15
41
45
11...

result:

ok 197451 numbers

Test #9:

score: 0
Accepted
time: 526ms
memory: 3736kb

input:

99606
110011011001101010010101101110011100110101
111110001011000010010110011001110111010101100110100001111
1111111111110101101011000101101101101110011110100001100010
00110110000101111000010011100010011110101000111110010011111110011011100001001111101001010000101010000100101111001001110010100001000100...

output:

45
66
67
227
261
108
39
44
204
26
72
249
44
130
44
80
39
180
23
148
157
66
201
157
150
151
184
137
252
102
139
36
51
216
9
17
141
216
253
241
92
220
52
139
125
75
98
162
202
2
50
117
170
46
154
95
132
202
23
154
222
210
17
91
39
163
145
184
98
225
35
12
163
197
247
78
28
85
207
177
145
65
1
101
231
...

result:

ok 99606 numbers

Test #10:

score: 0
Accepted
time: 469ms
memory: 3740kb

input:

39961
0010111101010101011101101111110000010000000011100101001100100001101101110110110111000100111010001110101000001011011011101110000111001011001000101000000110100111100110011010011
0011110111000100101111001001010100001011111111011001000110011001100000110110001101001110011100001010100100001010110100...

output:

218
247
101
564
482
45
274
1
342
161
263
364
76
233
581
28
229
134
514
690
722
234
109
555
553
696
481
383
88
78
510
226
603
498
175
10
307
542
333
731
447
608
153
304
193
427
372
242
383
640
664
93
126
434
176
69
361
547
418
518
372
63
439
359
15
249
394
311
194
341
423
202
90
594
595
206
141
154
3...

result:

ok 39961 numbers

Test #11:

score: 0
Accepted
time: 452ms
memory: 3672kb

input:

19900
00101000110101110100101101101000100001110011010110001000111000101000101100110110110010101010110011001
000100001101000100000000011001111100001010011100001010110010100111100000110100100010011110100011000001101100101010010110001100001000011100010001001111111011000111100011100001111111101100000010...

output:

117
1202
935
320
31
349
631
371
30
181
1132
764
708
1262
436
1222
960
1076
1310
1168
715
320
946
959
101
528
746
183
1347
641
765
1101
801
858
742
54
555
782
369
1085
175
496
566
793
804
197
540
25
727
1043
601
1197
1230
136
129
528
1442
962
1081
926
655
465
176
402
576
1089
117
1075
927
11
1350
185...

result:

ok 19900 numbers

Test #12:

score: 0
Accepted
time: 461ms
memory: 3768kb

input:

4031
0101001000010110001001000101110011010010110101001111001011010100001011000000011110000101010100111010110111001000101010101101011110001011000010101100111001110101000101001101001111011001100100101000010100110000010001110101101000110011001000001100000110000001101000100111100101001010111010000010001...

output:

6202
584
6509
657
1743
5982
1148
748
1575
6011
6040
5974
2214
5948
4292
4605
2487
2731
4044
1993
5214
6627
4551
1840
2417
244
6770
2494
1059
3867
4419
2657
4977
4832
5701
1563
1289
5763
1109
2331
2856
1656
1779
6475
5204
600
2179
1248
5753
3579
3725
977
2984
4648
5155
5718
4911
655
1706
930
3573
544...

result:

ok 4031 numbers

Test #13:

score: 0
Accepted
time: 436ms
memory: 3848kb

input:

1986
0010100001101000101100001101010011101001110001011101000101010011011000011000000011100110111111010011011010000001000100100001111010101000110000011001110011111100100011100000000101011010101001001011100001111010110011101001000101001110111011001001011111000101000111111101000111110100110100101110011...

output:

3575
158
10791
2517
10092
379
2714
4211
10875
864
7134
3087
9276
5867
4399
6739
7310
8962
1786
1864
6083
9574
2381
887
9533
6409
7472
101
9389
4962
8088
1381
4558
6064
11626
13564
9725
8062
9960
7461
4006
8686
7926
992
10332
5300
4297
1258
3574
8521
9338
4518
1454
9619
6148
1728
1693
8778
4767
9005
...

result:

ok 1986 numbers

Test #14:

score: 0
Accepted
time: 441ms
memory: 5488kb

input:

200
11110101000100010101100111001011001100011010111101111001010110111100011000110100000101001011100110000001101101010111001001111000011000110101100001101111000010010001110011011011100100000110001101010000111111011010001010000111111010100110001110111011010001001010010111100000000101000000110110100101...

output:

99387
101499
105048
107208
147040
123233
104316
147653
129648
112911
123645
68175
86293
59301
9216
20367
135688
57251
140800
103068
15284
5563
54435
56802
115931
5470
10007
102744
17459
94573
120878
36051
60255
25462
37271
89381
25412
60168
121131
103391
6313
72623
18730
112666
126652
20613
126380
1...

result:

ok 200 numbers

Test #15:

score: 0
Accepted
time: 453ms
memory: 18344kb

input:

32
001000110111000110001001011111010111101110100100100001101101110100111101110100011001010110101100011010111100110110001100101000100011011101100111111101100101110110011010011011110100101111000001111110101110010010100111000101000000001000100000010001111011011000110011011100111100010000110010101100011...

output:

789128
429343
538544
596982
409959
372382
359690
572322
247119
172312
601326
439990
866424
598385
696599
12351
835984
854751
639495
121099
381828
201978
2258
217
2648
1957
880
85
3
3
6
2

result:

ok 32 numbers

Test #16:

score: 0
Accepted
time: 483ms
memory: 85260kb

input:

17
001011111100001100101011100000000011110111100110100110111010110100001111000010011111111110010001101000100011110101111011001011111011000010011001100000110101001101100101010000101110010010101101110110000101001101011100011001101010101010011000101000001000001001010111100001000010011100101100011001111...

output:

4673925
490734
133816
1140925
276336
3107252
202768
110731
148861
35367
14100
4549
1219
1698
15
2
1

result:

ok 17 numbers

Test #17:

score: -100
Runtime Error

input:

1
0010000000010010001000000001001000100000000100100010000000010010001000000001001000100000000100100010000000010010001000000001001000100000000100100010000000010010001000000001001000100000000100100010000000010010001000000001001000100000000100100010000000010010001000000001001000100000000100100010000000...

output:


result: