QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#95888 | #6299. Binary String | psc233 | RE | 806ms | 85260kb | C++14 | 2.1kb | 2023-04-12 12:17:30 | 2023-04-12 12:17:33 |
Judging History
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...