QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#245944#4669. Genetic ModificationsaccgjWA 2ms9868kbC++142.0kb2023-11-10 14:44:342023-11-10 14:44:35

Judging History

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

  • [2023-11-10 14:44:35]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9868kb
  • [2023-11-10 14:44:34]
  • 提交

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]-'0');
	for(int i=1;i<=n;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: 9868kb

input:

BBAAABBAAABAAA
BAAB

output:

NO

result:

wrong answer you didn't find a solution but jury did