QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#246299#4669. Genetic ModificationsJudgelightWA 1ms5808kbC++141.1kb2023-11-10 18:47:522023-11-10 18:47:52

Judging History

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

  • [2023-11-10 18:47:52]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5808kb
  • [2023-11-10 18:47:52]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1e5+10;
char a[N],b[N];
int n,m,nex[N][2],pre[N][2];
int mark[N],mrk[N];
bool vis[N];
int main(){
	scanf("%s%s",a+1,b+1);
	n=strlen(a+1),m=strlen(b+1);
	for(int i=1;i<=n;++i)a[i]^=48;
	for(int i=1;i<=m;++i)b[i]^=48;
	for(int i=n;i>=1;--i){
		nex[i][a[i]]=i;
		nex[i][a[i]^1]=nex[i+1][a[i]^1];
	}
	for(int i=1;i<=n;++i){
		pre[i][a[i]]=i;
		pre[i][a[i]^1]=pre[i-1][a[i]^1];
	}
	for(int i=1,j=1;i<=m;++i,++j){
		if(!nex[j][b[i]]){
			puts("NO");
			return 0;
		}
		j=nex[j][b[i]],mark[j]=i;
//		printf("mark[%d]=%d\n",j,i);
	}
	for(int i=m,j=n;i>=1;--i,--j){
		if(!pre[j][b[i]]){
			puts("NO");
			return 0;
		}
		if(a[j]==b[i])j=pre[j][b[i]^1]+1;
		else j=pre[j][b[i]];
//		printf("mrk[%d]=%d\n",j,i);
		if(mark[j]==i){
			puts("YES");
			for(int k=1;k<=n;++k)
				if(k<=j&&mark[k]||k>j&&mrk[k]){
					printf("%d ",k);
				}
			return 0;
		}
		mrk[j]=i;
		if(i==1&&(pre[j][0]==0||pre[j][1]==0)){
			puts("YES");
			for(int k=1;k<=n;++k)
				if(mrk[k])
					printf("%d ",k);
			return 0;
		}
	}
	puts("NO");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 5808kb

input:

BBAAABBAAABAAA
BAAB

output:

NO

result:

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