QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#246312 | #4669. Genetic Modifications | Judgelight | WA | 0ms | 3812kb | C++14 | 988b | 2023-11-10 18:57:01 | 2023-11-10 18:57:02 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define eb emplace_back
#define mk make_pair
#define N 100009
using namespace std;
int n,m,f[N],g[N],sum[N][2];char s[N],t[N];
bool check(int l,int r){if(l>r)return 1;return !(sum[r][0]-sum[l-1][0])||!(sum[r][1]-sum[l-1][1]);}
signed main(){
scanf("%s",s+1),n=strlen(s+1);scanf("%s",t+1),m=strlen(t+1);
for(int i=1;i<=n;i++)sum[i][0]=sum[i-1][0]+(s[i]=='0'),sum[i][1]=sum[i-1][1]+(s[i]=='1');
for(int i=1;i<=m;i++){
f[i]=f[i-1]+1;
while(f[i]<=n&&s[f[i]]!=t[i])f[i]++;
}
if(f[m]>n){printf("NO");return 0;}
g[m+1]=n+1;
for(int i=m;i>=1;i--){
g[i]=g[i+1]-1;
while(g[i]>=1&&s[g[i]]!=t[i])g[i]--;
while(g[i]>1&&s[g[i]-1]==t[i]&&check(g[i],g[i+1]-1))g[i]--;
}
for(int i=0;i<=m;i++){
if(f[i]>g[i+1])continue;
if(check(f[i]+1,g[i+1]-1)){
printf("YES\n");
for(int j=1;j<=i;j++)printf("%d ",f[j]);
for(int j=i+1;j<=m;j++)printf("%d ",g[j]);
return 0;
}
}
printf("NO");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3812kb
input:
BBAAABBAAABAAA BAAB
output:
YES 1 3 8 11
result:
wrong answer wrong solution [2]