QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#246312#4669. Genetic ModificationsJudgelightWA 0ms3812kbC++14988b2023-11-10 18:57:012023-11-10 18:57:02

Judging History

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

  • [2023-11-10 18:57:02]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3812kb
  • [2023-11-10 18:57:01]
  • 提交

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,f[N],g[N],sum[N][2];char s[N],t[N];
bool check(int l,int r){if(l>r)return 1;return !(sum[r][0]-sum[l-1][0])||!(sum[r][1]-sum[l-1][1]);}
signed main(){
	scanf("%s",s+1),n=strlen(s+1);scanf("%s",t+1),m=strlen(t+1);
	for(int i=1;i<=n;i++)sum[i][0]=sum[i-1][0]+(s[i]=='0'),sum[i][1]=sum[i-1][1]+(s[i]=='1');
	for(int i=1;i<=m;i++){
		f[i]=f[i-1]+1;
		while(f[i]<=n&&s[f[i]]!=t[i])f[i]++;
	}
	if(f[m]>n){printf("NO");return 0;}
	g[m+1]=n+1;
	for(int i=m;i>=1;i--){
		g[i]=g[i+1]-1;
		while(g[i]>=1&&s[g[i]]!=t[i])g[i]--;
		while(g[i]>1&&s[g[i]-1]==t[i]&&check(g[i],g[i+1]-1))g[i]--;
	}
	for(int i=0;i<=m;i++){
		if(f[i]>g[i+1])continue;
		if(check(f[i]+1,g[i+1]-1)){
			printf("YES\n");
			for(int j=1;j<=i;j++)printf("%d ",f[j]);
			for(int j=i+1;j<=m;j++)printf("%d ",g[j]);
			return 0;
		}
	}
	printf("NO");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

BBAAABBAAABAAA
BAAB

output:

YES
1 3 8 11 

result:

wrong answer wrong solution [2]