QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#246291 | #4669. Genetic Modifications | accgj | WA | 1ms | 6184kb | C++14 | 1.6kb | 2023-11-10 18:43:27 | 2023-11-10 18:43:28 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
char s[1000001],t[1000001];
int n,m;
int sum[1000001];
int f[1000001],g[1000001];
int main()
{
scanf("%s",s);scanf("%s",t);
n=strlen(s),m=strlen(t);
for(int i=1;i<=n;i++)sum[i]=(s[i-1]-'A')+sum[i-1];
sum[n+1]=sum[n];
for(int i=1;i<=m;i++)
{
bool flag=0;
for(int j=f[i-1]+1;j<=n;j++)
{
if(sum[j-1]-sum[f[i-1]]==0 or sum[j-1]-sum[f[i-1]]==j-1-f[i-1])
{
if(t[i-1]==s[j-1])
{
f[i]=j;flag=1;
break;
}
}
}
if(flag==0)
{
printf("NO\n");return 0;
}
}
g[m+1]=n+1;
for(int i=m;i>=1;i--)
{
bool flag=0;
for(int j=g[i+1]-1;j>=1;j--)
{
if(sum[g[i+1]-1]-sum[j]==0 or sum[g[i+1]-1]-sum[j]==g[i+1]-1-j)
{
if(t[i-1]==s[j-1])
{
if(j==1)
{
g[i]=j;flag=1;break;
}
if(sum[g[i+1]-1]-sum[j-1]==0 or sum[g[i+1]-1]-sum[j-1]==g[i+1]-1-j+1)
{
if(t[i-1]==s[j-2])
{
continue;
}
}
g[i]=j;flag=1;break;
}
}
}
if(flag==0)
{
g[i]=-1;break;
}
}
if(g[1]!=-1)
{
if(sum[g[1]-1]-sum[0]==0 or sum[g[1]-1]-sum[0]==g[1]-1)
{
printf("YES\n");
for(int i=1;i<=m;i++)printf("%d ",g[i]);
printf("\n");
return 0;
}
}
for(int i=1;i<=m;i++)
{
if(g[i+1]==-1)continue;
if(g[i+1]<=f[i])continue;
if(sum[g[i+1]-1]-sum[f[i]]==0 or sum[g[i+1]-1]-sum[f[i]]==g[i+1]-1-f[i])
{
printf("YES\n");
for(int j=1;j<=m;j++)
{
if(j<=i)printf("%d ",f[j]);
else printf("%d ",g[j]);
}
printf("\n");
return 0;
}
}
printf("NO\n");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5804kb
input:
BBAAABBAAABAAA BAAB
output:
YES 2 5 8 11
result:
ok good solution
Test #2:
score: 0
Accepted
time: 1ms
memory: 5876kb
input:
ABABABABAB ABAB
output:
NO
result:
ok no solution
Test #3:
score: 0
Accepted
time: 0ms
memory: 6184kb
input:
BBAAAAABBAAAAAABBABAABBBBBAABBBAAABABBABABBBAAABBAAAABBBBBABAABBBAABBBBBBBABBABABBAAAABBAAAABAAAABBABAAAAAAABBBBAAAAAABAABABBAAAAABBBBAABABABAAAAABBBABABBAABABBBBAABAABBBBBABBABABBAAABBAAAABBBABBABAAAABBBAABAAABBBAAAAAAAAAAAAABABBAABBBBABABAABBBBABAABBAAABABBBBAAAAAAAABBAAAABBABABABBBAAABAABBABBAAAA...
output:
NO
result:
ok no solution
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 5980kb
input:
BABABAABABBABAAAAABAABBAAAAABABABBABABBBBBBBAAAAAAABAAAAABAABBABBABABBBABBBAAAABBBABABBAAAABBBAABBBBBBBAAAABAAAABBBBABBAABAABBBAABBBBABAABABBBBAABABBABBAABAABBBBBAAABBAABABBBBAABABBABAABAAAABBABABAABBBABBBBABABABABAAABBABABABABBABAABBBBABAABBABBBBABABBABBBBBAABBBBBAAABAABAAAABBBBBABBABABABBBBABBBABA...
output:
YES 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer Integer 0 violates the range [1, 13058]