QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#246109#4669. Genetic ModificationsSham_DevourWA 1ms5872kbC++142.3kb2023-11-10 16:15:512023-11-10 16:15:53

Judging History

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

  • [2023-11-10 16:15:53]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5872kb
  • [2023-11-10 16:15:51]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5,M=1e5+5;
bool f[N][N],F[M][25];
int sum[M];
char a[M],b[M];
int n,m,la[M],s=1,fl;
vector<int> vec;
void solve1() {
	for(int i=1;i<=n;i++) {
		la[i]=s;
		if(a[i]!=a[i+1]) s=i+1;
	}
	f[0][0]=1;
	for(int i=0;i<=n;i++) sum[i+1]=sum[i]+f[i][0];
	for(int j=1;j<=m;j++) {
		for(int i=1;i<=n;i++) {
			if(a[i]==b[j]) {
				if(i==la[i]) f[i][j]=(sum[i]-sum[la[i-1]-1])?1:0;
				else f[i][j]=(sum[i]-sum[la[i]-1])?1:0;
			}
		}
		for(int i=0;i<=n;i++) sum[i+1]=sum[i]+f[i][j];
	}
	for(int i=n;i>=1;i--) {
		if(f[i][m]) {
			int pos=i,w=m;
			while(w>0) {
				vec.push_back(pos);
				int L=(pos==la[pos])?(la[pos-1]-1):(la[pos]-1);
				for(int j=pos-1;j>=L;j--)
					if(f[j][w-1]) {
						pos=j;
						w--;
						break;
					}
			}
			puts("YES");
			for(int j=vec.size()-1;j>=0;j--) printf("%d ",vec[j]);
			fl=1;
			break;
		}
		if(i<n&&a[i]!=a[i+1]) break;
	}
	if(!fl) puts("NO");
}
void solve2() {
	for(int i=1;i<=n;i++) {
		la[i]=s;
		if(a[i]!=a[i+1]) s=i+1;
	}
	F[0][0]=1;
	for(int i=0;i<=n;i++) sum[i+1]=sum[i]+F[i][0];
	for(int j=1;j<=m;j++) {
		for(int i=1;i<=n;i++) {
			if(a[i]==b[j]) {
				if(i==la[i]) F[i][j]=(sum[i]-sum[la[i-1]-1])?1:0;
				else F[i][j]=(sum[i]-sum[la[i]-1])?1:0;
			}
		}
		for(int i=0;i<=n;i++) sum[i+1]=sum[i]+F[i][j];
	}
	for(int i=n;i>=1;i--) {
		if(F[i][m]) {
			int pos=i,w=m;
			while(w>0) {
				vec.push_back(pos);
				int L=(pos==la[pos])?(la[pos-1]-1):(la[pos]-1);
				for(int j=pos-1;j>=L;j--)
					if(F[j][w-1]) {
						pos=j;
						w--;
						break;
					}
			}
			puts("YES");
			for(int j=vec.size()-1;j>=0;j--) printf("%d ",vec[j]);
			fl=1;
			break;
		}
		if(i<n&&a[i]!=a[i+1]) break;
	}
	if(!fl) puts("NO");
}
void solve3() {
	a[0]=a[1];a[n+1]=a[n];int T=1,tt=0;
	for(int i=1;i<=n;i++)
		if(a[i]!=a[i+1]||a[i]!=a[i-1]) {
			if(T<=m&&a[i]==b[T]) {
				vec.push_back(i);
				T++;tt=0;
			} else {
				tt++;
				if(tt>=2) {
					puts("NO");
					fl=1;
					break;
				}
			}
		}
	if(!fl) {
		if(T>m) {
			puts("YES");
			for(int j=0;j<vec.size();j++) printf("%d ",vec[j]);
		} else puts("NO");
	} 
}
int main() {
	scanf("%s%s",a+1,b+1);n=strlen(a+1);m=strlen(b+1);
	if(n<=2000&&m<=2000) solve1();
	else if(m<=20) solve2();
	else solve3();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5872kb

input:

BBAAABBAAABAAA
BAAB

output:

YES
2 5 8 11 

result:

ok good solution

Test #2:

score: 0
Accepted
time: 1ms
memory: 5632kb

input:

ABABABABAB
ABAB

output:

NO

result:

ok no solution

Test #3:

score: 0
Accepted
time: 1ms
memory: 5680kb

input:

BBAAAAABBAAAAAABBABAABBBBBAABBBAAABABBABABBBAAABBAAAABBBBBABAABBBAABBBBBBBABBABABBAAAABBAAAABAAAABBABAAAAAAABBBBAAAAAABAABABBAAAAABBBBAABABABAAAAABBBABABBAABABBBBAABAABBBBBABBABABBAAABBAAAABBBABBABAAAABBBAABAAABBBAAAAAAAAAAAAABABBAABBBBABABAABBBBABAABBAAABABBBBAAAAAAAABBAAAABBABABABBBAAABAABBABBAAAA...

output:

NO

result:

ok no solution

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 5720kb

input:

BABABAABABBABAAAAABAABBAAAAABABABBABABBBBBBBAAAAAAABAAAAABAABBABBABABBBABBBAAAABBBABABBAAAABBBAABBBBBBBAAAABAAAABBBBABBAABAABBBAABBBBABAABABBBBAABABBABBAABAABBBBBAAABBAABABBBBAABABBABAABAAAABBABABAABBBABBBBABABABABAAABBABABABABBABAABBBBABAABBABBBBABABBABBBBBAABBBBBAAABAABAAAABBBBBABBABABABBBBABBBABA...

output:

NO

result:

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