QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#763829 | #6299. Binary String | lyx | WA | 191ms | 3824kb | C++14 | 1.2kb | 2024-11-19 22:17:41 | 2024-11-19 22:17:43 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define rll register ll
#define ull unsigned ll
#define ri register int
#define fo(i,x,y) for(ri i=(x);i<=(y);++i)
#define fu(i,x,y) for(ri i=(x);i<(y);++i)
#define fd(i,x,y) for(ri i=(x);i>=(y);--i)
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=1e7+5;
int T,mx[2],pi[N];string str;
inline void wt(ri x){
if(x>9)wt(x/10);
putchar(x%10+'0');
}
int main(){
scanf("%d",&T);
while(T--){
cin>>str;ri ln=str.size();
ri w=ln;
fu(i,0,ln){
if(str[i]!=str[ln-1]){
w=i;
break;
}
}
ri op=str[w]-'0';
if(w==ln){
puts("1");
continue;
}
// printf("%d\n",w);
fu(i,0,ln-w)str[i]=str[i+w];
fu(i,ln-w,ln)str[i]=(op^1)+'0';
mx[0]=mx[1]=0;
ri la=0;
fu(i,0,ln){
if(i==ln-1||str[i]!=str[i+1]){
ri o=str[i]-'0';
mx[o]=max(mx[o],i-la+1);
la=i+1;
}
}
fd(i,ln,1)str[i]=str[i-1];
pi[1]=0;str[0]='#';
fo(i,2,ln){
ri j=pi[i-1];
while(j&&str[j+1]!=str[i])j=pi[j];
pi[i]=j+(str[j+1]==str[i]);
}
ri s=min(mx[0],mx[1]);
s+=ln-pi[ln];
wt(s-1);putchar('\n');
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3824kb
input:
3 1 001001 0001111
output:
1 3 9
result:
ok 3 number(s): "1 3 9"
Test #2:
score: -100
Wrong Answer
time: 191ms
memory: 3784kb
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 19 19 19 20 21 18 18 18 19 18 18 19 20 19 19 19 19 20 20 21 22 18 18 18 19 18 18 19 20 18 18 18 19 19 19 20 21 19 19 19 19 19 19 19 20 20 20 20 20 21 21 22 23 18 18 18 19 18 18 19 20 18 18 18 19 19 19 20 21 18 18 18 19 18 18 19 20 19 19 19 19 20 20 21 22 19 19 19 19 1...
result:
wrong answer 12th numbers differ - expected: '20', found: '19'