QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#246291#4669. Genetic ModificationsaccgjWA 1ms6184kbC++141.6kb2023-11-10 18:43:272023-11-10 18:43:28

Judging History

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

  • [2023-11-10 18:43:28]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6184kb
  • [2023-11-10 18:43:27]
  • 提交

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]