QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #360582 | #6299. Binary String | mazihang2022 | WA | 114ms | 5900kb | C++14 | 3.1kb | 2024-03-21 22:05:27 | 2024-03-21 22:05:27 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
#define pii pair<int,int>
#define isz(v) (int)(v.size())
using namespace std;
const int maxn=200005;
const int inf=0x3f3f3f3f;
namespace Solve {
int a[maxn];
int res[maxn];
int fail[maxn];
void clear() {
}
void main(int tid) {
string s;
cin>>s;
int n=isz(s);
for(int i=1;i<=n;i++) {
a[i]=s[i-1]-'0';
}
int c=accumulate(a+1,a+n+1,0);
if(!c||c==n) {
cout<<"1\n";
return ;
}
if(c<=n-c) {
for(int i=1;i<=n;i++) {
a[i]^=1;
}
reverse(a+1,a+n+1);
}
int sum=0,mi=inf,pos=0;
for(int i=1;i<=n;i++) {
sum+=a[i]?1:-1;
if(sum<mi) {
mi=sum;
pos=i;
}
}
assert(pos);
rotate(a+1,a+pos+1,a+n+1);
if(a[n]==1) {
int p=n;
while(a[p]==1) {
p--;
}
rotate(a+1,a+p+1,a+n+1);
}
// for(int i=1;i<=n;i++) {
// cerr<<a[i]<<" ";
// }
// cerr<<"\n";
int ans=0;
deque<array<int,5>> vs;
auto insert=[&](int p,int len,int tim,int l,int r) {
while(isz(vs)&&vs.back()[0]&&!p) {
auto t=vs.back();
vs.pop_back();
if(t[1]<len) {
len-=t[1];
tim+=t[1];
ans=max(ans,t[2]+t[1]);
} else if(t[1]==len) {
ans=max(ans,t[2]+t[1]);
ans=max(ans,tim+len);
return ;
} else {
ans=max(ans,tim+len);
vs.push_back({t[0],t[1]-len,t[2]+len,t[3],t[4]});
return ;
}
}
vs.push_back({p,len,tim,l,r});
};
for(int i=1;i<=n;i++) {
int j=i;
while(j<=n&&a[i]==a[j]) {
j++;
}
insert(a[i],j-i,0,i,j-1);
i=j-1;
}
// cerr<<ans<<"\n";
fill(res+1,res+n+1,0);
for(auto p:vs) {
// cerr<<"p: "<<p[0]<<" "<<p[1]<<" "<<p[2]<<" "<<p[3]<<" "<<p[4]<<"\n";
for(int i=(p[3]+ans-1)%n+1,c=1;c<=p[1];c++,i=i%n+1) {
res[i]=1;
}
}
// for(int i=1;i<=n;i++) {
// cerr<<res[i]<<" ";
// }
// cerr<<"\n";
for(int i=1;i<=n;i++) {
if(res[i]) {
for(int p=i,j=i%n+1;j!=i;p=j,j=j%n+1) {
if(!res[j]) {
res[j]=res[p]^1;
}
}
break;
}
}
// for(int i=1;i<=n;i++) {
// cerr<<res[i]<<" ";
// }
// cerr<<"\n";
int j=0;
for(int i=2;i<=n;i++) {
while(j&&res[i]!=res[j+1]) {
j=fail[j];
}
if(res[i]==res[j+1]) {
j++;
}
fail[i]=j;
}
if(n%(n-fail[n])==0) {
ans+=n-fail[n];
} else {
ans+=n;
}
cout<<ans-1<<"\n";
}
void init() {
}
}
signed main() {
#ifndef ONLINE_JUDGE
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T=1;
cin>>T;
Solve::init();
for(int t=1;t<=T;t++) {
Solve::main(t);
Solve::clear();
}
#ifndef ONLINE_JUDGE
cerr<<"Time: "<<(1.0*clock()/CLOCKS_PER_SEC)*1000<<"ms\n";
#endif
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5900kb
input:
3 1 001001 0001111
output:
1 3 9
result:
ok 3 number(s): "1 3 9"
Test #2:
score: -100
Wrong Answer
time: 114ms
memory: 3612kb
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'