QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#246352#4669. Genetic ModificationsQZJ123456WA 1ms3416kbC++141.4kb2023-11-10 19:19:482023-11-10 19:19:48

Judging History

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

  • [2023-11-10 19:19:48]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3416kb
  • [2023-11-10 19:19:48]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,m;
char s[100005],t[100005];
int nxt[100005][2],lst[100005][2],l[100005];
struct node{
	int l,r;
	node(){}
	node(int l_,int r_){
		l=l_,r=r_;
	}
}cur,a[100005];
node merge(node x,node y){
	if(x.l>x.r)return y;
	if(y.l>y.r)return x;
	return node(min(x.l,y.l),max(x.r,y.r));
}
bool ck[100005];
bool in(int l,int r,int x){
	return (l<=x)&&(x<=r);
}
vector<int>out;
int main(){
	scanf("%s%s",t+1,s+1);
	n=strlen(s+1),m=strlen(t+1);
	for(int i=1;i<=m;i++){
		lst[i][0]=lst[i-1][0],lst[i][1]=lst[i-1][1];
		lst[i][t[i]-'0']=i;
	}
	nxt[m+1][0]=nxt[m+1][1]=1e9;
	for(int i=m;i;i--){
		nxt[i][0]=nxt[i+1][0],nxt[i][1]=nxt[i+1][1];
		nxt[i][t[i]-'0']=i;
	}
	int lls=-1;
	for(int i=1;i<=n;i++){
		int p=l[(s[i-1]-'0')^1];
		if(p!=lls){
			cur=node(1e9,0);
			for(int j=p;j<i;j++)cur=merge(cur,a[j]);
			lls=p;
		}
		a[i]=node(nxt[cur.l+1][s[i]-'0'],lst[min(m,cur.r+1)][s[i]-'0']);
		cur=merge(a[i],cur);
		l[s[i]-'0']=i;
	}
	ck[n]=1;
	for(int i=n-1;i;i--)if(s[i+1]==s[n])ck[i]=1;else break;
	int pos=-1;
	for(int i=1;i<=n;i++){
		if(in(a[i].l,a[i].r,m)&&ck[i])pos=i;
	}
	if(pos==-1){
		puts("NO");
		exit(0);
	}
	out.push_back(pos);
	puts("YES");
	for(int i=m-1;i;i--){
		pos--;
		while(pos){
			if(in(a[pos].l,a[pos].r,i)&&s[pos]==t[i])break;
			pos--;
		}
		out.push_back(pos);
	}
	reverse(out.begin(),out.end());
	for(auto to:out)printf("%d ",to);
	return 0;
}

詳細信息

Test #1:

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

input:

BBAAABBAAABAAA
BAAB

output:

NO

result:

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