QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#246811 | #4669. Genetic Modifications | accgj | WA | 2ms | 11972kb | C++14 | 2.0kb | 2023-11-11 09:58:00 | 2023-11-11 09:58:01 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
char s[200002],t[200002];
int n,m;
bool mark[2002][2002];
pair<int,int> f[2002][2002];
int sum[200002];
int las[200002];
int ad[1000001];
pair<int,int> f2[100001][21];
bool mark2[100001][21];
stack<int> s1;
inline void subtask1()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s[i-1]!=t[j-1])continue;
if(j==1)
{
if(sum[i-1]!=0 and sum[i-1]!=i-1)continue;
mark2[i][j]=1;las[j]=max(las[j],i);
f2[i][j]=make_pair(0,0);continue;
}
if(ad[i]==i)
{
if(las[j-1]>=ad[i-1]-1 and las[j-1]<i)
{
mark2[i][j]=1;
f2[i][j]=make_pair(las[j-1],j-1);
las[j]=max(las[j],i);
}
}
}
}
for(int i=n;i>=1;i--)
{
if(!mark2[i][m])continue;
if(sum[n]-sum[i]!=0 and sum[n]-sum[i]!=n-i)break;
printf("YES\n");
for(int j=i,k=m;j!=0;j=f2[j][k].first,k--)s1.push(j);
while(!s1.empty())printf("%d ",s1.top()),s1.pop();
printf("\n");
return ;
}
printf("NO\n");
}
int main()
{
scanf("%s",s);scanf("%s",t);
n=strlen(s),m=strlen(t);
for(int i=0;i<n;i++)sum[i+1]=(s[i]-'A');
for(int i=1;i<=n+1;i++)sum[i]+=sum[i-1];
ad[1]=1;
for(int i=1;i<n;i++)
{
if(s[i-1]==s[i])ad[i+1]=ad[i];
else ad[i+1]=i+1;
}
if(n>2000)
{
subtask1();return 0;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s[i-1]!=t[j-1])continue;
if(j==1)
{
if(sum[i-1]!=0 and sum[i-1]!=i-1)continue;
mark[i][j]=1;las[j]=max(las[j],i);
f[i][j]=make_pair(0,0);continue;
}
if(ad[i]==i)
{
if(las[j-1]>=ad[i-1]-1 and las[j-1]<i)
{
mark[i][j]=1;
f[i][j]=make_pair(las[j-1],j-1);
las[j]=max(las[j],i);
}
}
}
}
for(int i=n;i>=1;i--)
{
if(!mark[i][m])continue;
if(sum[n]-sum[i]!=0 and sum[n]-sum[i]!=n-i)break;
printf("YES\n");
for(int j=i,k=m;j!=0;j=f[j][k].first,k--)s1.push(j);
while(!s1.empty())printf("%d ",s1.top()),s1.pop();
printf("\n");
return 0;
}
printf("NO\n");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 11972kb
input:
BBAAABBAAABAAA BAAB
output:
NO
result:
wrong answer you didn't find a solution but jury did