QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#763829#6299. Binary StringlyxWA 191ms3824kbC++141.2kb2024-11-19 22:17:412024-11-19 22:17:43

Judging History

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

  • [2024-11-19 22:17:43]
  • 评测
  • 测评结果:WA
  • 用时:191ms
  • 内存:3824kb
  • [2024-11-19 22:17:41]
  • 提交

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'