QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#246030#4669. Genetic ModificationsJudgelightWA 0ms20052kbC++142.3kb2023-11-10 15:36:552023-11-10 15:36:57

Judging History

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

  • [2023-11-10 15:36:57]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:20052kb
  • [2023-11-10 15:36:55]
  • 提交

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,_0[N],_1[N];char s[N],t[N];
namespace solve1{
	int f[2009][2009],ans[2009],lst[2009];
	int mian(){
		memset(lst,-1,sizeof(lst));memset(f,-1,sizeof(f));
		f[0][0]=0,lst[0]=0;
		for(int i=1;i<=n;i++){
			int l=min(_0[i-1],_1[i-1]);
			for(int j=m;j;j--){
				if(s[i]!=t[j])continue;
				if(lst[j-1]>=l)f[i][j]=lst[j-1],lst[j]=i;
			}
		}
		for(int i=min(_0[n],_1[n]);i<=n;i++){
			if(~f[i][m]){
				printf("YES\n");
				for(int j=m;j>=1;j--){
					ans[j]=i,i=f[i][j];
				}
				for(int j=1;j<=m;j++)printf("%d ",ans[j]);
				return 0;
			}
		}
		printf("NO");
		return 0;
	}
}
namespace solve2{
	int f[N][23],ans[N],lst[N];
	int mian(){
		memset(lst,-1,sizeof(lst));memset(f,-1,sizeof(f));
		f[0][0]=0,lst[0]=0;
		for(int i=1;i<=n;i++){
			int l=min(_0[i-1],_1[i-1]);
			for(int j=m;j;j--){
				if(s[i]!=t[j])continue;
				if(lst[j-1]>=l)f[i][j]=lst[j-1],lst[j]=i;
			}
		}
		for(int i=min(_0[n],_1[n]);i<=n;i++){
			if(~f[i][m]){
				printf("YES\n");
				for(int j=m;j>=1;j--){
					ans[j]=i,i=f[i][j];
				}
				for(int j=1;j<=m;j++)printf("%d ",ans[j]);
				return 0;
			}
		}
		printf("NO");
		return 0;
	}
}
namespace solve3{
	vector<pair<int,int> >v;int p[N];
	int mian(){
		v.eb(mk(1,1));
		for(int i=2;i<=n;i++)if(s[i]==s[i-1])v.back().second=i;else v.eb(mk(i,i));
		int j=0;
		if(s[v[j].first]!=t[1])j++;
		if(j>=v.size()){printf("NO");return 0;}
		!j?p[1]=v[j].second:p[1]=v[j].first;
		for(int i=2;i<=m;i++){
			j++;if(j>=v.size()){printf("NO");return 0;}
			p[i-1]==v[j-1].second?p[i]=v[j].second:p[i]=v[j].first;
		}
		bool vis[2];vis[0]=vis[1]=0;
		for(int i=p[m]+1;i<=n;i++)vis[s[i]-'0']=1;
		if(vis[0]&&vis[1]){printf("NO");return 0;}
		printf("YES\n");
		for(int i=1;i<=m;i++)printf("%d ",p[i]);
		return 0;
	}
}
int main(){
	scanf("%s",s+1),n=strlen(s+1);
	scanf("%s",t+1),m=strlen(t+1);
	for(int i=1;i<=n;i++){
		_0[i]=_0[i-1],_1[i]=_1[i-1];
		s[i]=='0'?_0[i]=i:_1[i]=i;
	}
	bool flag=1;
	for(int i=2;i<=m;i++)if(t[i]==t[i-1]){flag=0;break;}
	if(!flag){if(n<=2000)solve1::mian();else if(m<=20)solve2::mian();else printf("NO");}
	else solve3::mian();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 20052kb

input:

BBAAABBAAABAAA
BAAB

output:

YES
2 4 5 6 

result:

wrong answer wrong solution [2]