QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#246328#4669. Genetic ModificationsJudgelightWA 1ms5980kbC++141.1kb2023-11-10 19:05:472023-11-10 19:05:49

Judging History

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

  • [2023-11-10 19:05:49]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5980kb
  • [2023-11-10 19:05:47]
  • 提交

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]-=65;
	for(int i=1;i<=m;++i)b[i]-=65;
//	for(int i=1;i<=n;++i)a[i]^=48;
//	for(int i=1;i<=m;++i)b[i]^=48;
	nex[n+1][0]=nex[n+1][1]=n+1;
	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]]==n+1){
			if(n>=1000)puts("-----");
			puts("NO");
			return 0;
		}
		j=nex[j][b[i]],mark[i]=j;
	}
	for(int i=m,j=n;i>=1;--i,--j){
		if(!pre[j][b[i]])
			break;
		if(a[j]==b[i])j=pre[j][b[i]^1]+1;
		else j=pre[j][b[i]];
		mrk[i]=j;
	}
	for(int i=0;i<=m;++i){
		if(mark[i]<mrk[i+1]&&max(nex[mark[i]+1][0],nex[mark[i]+1][1])>=mrk[i+1]){
			puts("YES");
			for(int j=1;j<=i;++j)printf("%d ",mark[j]);
			for(int j=i+1;j<=m;++j)printf("%d ",mrk[j]);
			return 0;
		}
	}
	puts("NO");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3832kb

input:

BBAAABBAAABAAA
BAAB

output:

YES
2 5 8 11 

result:

ok good solution

Test #2:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

ABABABABAB
ABAB

output:

NO

result:

ok no solution

Test #3:

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

input:

BBAAAAABBAAAAAABBABAABBBBBAABBBAAABABBABABBBAAABBAAAABBBBBABAABBBAABBBBBBBABBABABBAAAABBAAAABAAAABBABAAAAAAABBBBAAAAAABAABABBAAAAABBBBAABABABAAAAABBBABABBAABABBBBAABAABBBBBABBABABBAAABBAAAABBBABBABAAAABBBAABAAABBBAAAAAAAAAAAAABABBAABBBBABABAABBBBABAABBAAABABBBBAAAAAAAABBAAAABBABABABBBAAABAABBABBAAAA...

output:

NO

result:

ok no solution

Test #4:

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

input:

BABABAABABBABAAAAABAABBAAAAABABABBABABBBBBBBAAAAAAABAAAAABAABBABBABABBBABBBAAAABBBABABBAAAABBBAABBBBBBBAAAABAAAABBBBABBAABAABBBAABBBBABAABABBBBAABABBABBAABAABBBBBAAABBAABABBBBAABABBABAABAAAABBABABAABBBABBBBABABABABAAABBABABABABBABAABBBBABAABBABBBBABABBABBBBBAABBBBBAAABAABAAAABBBBBABBABABABBBBABBBABA...

output:

YES
1 2 4 5 6 8 9 10 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 61 63 64 66 67 69 70 71 72 73 74 75 76 77 78 79 80 81 83 85 86 87 88 89 90 91 92 95 96 97 98 99 100 101 102 104 105 106 107 108 109 110 11...

result:

ok good solution

Test #5:

score: 0
Accepted
time: 0ms
memory: 5284kb

input:

BAABBBBBBAAABABABAAAAABAABBAAABBAABBBAABABBBABBABBBABBBBABAABAAAAABBBBBBBABABABAABABAABAABBBBBBABABABABBABBBBAABAABBAAABABBAAAAAAABBAAAAAAAABAAABABBAAABABABBBABAAABBBAABAABBABBBBBBBBBABBBABBBABBAABAABBABABBBBAAAABABAABAABABBABBABBBBBAABABABBBBBABAABBABABAABBABAABABBBBABABBBBBBABBBABABBAAABBAAABBABBA...

output:

NO

result:

ok no solution

Test #6:

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

input:

BBAABBAAABBBBAAABABBBABBBAABABAABBBABABBBAABBBBBBABBBAABABBBAAAAABABBABAABBAABABAABBAAABBBABAABBBAABAABABABBBBAABBBBBBBBBBBABBABABABBABBAAAAAAABAABABAABBABBABABBBBBAABBABBAABAABBBABBABBAABBBAAABBAAABABBBBBAAAABBAAABBAABABBABAABBBBAABBBAAAAAABBBAAAAABBBAAAABAABAAABBBAAABABBBABBBBBBBBAABABBABBBABAABAA...

output:

NO

result:

ok no solution

Test #7:

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

input:

BABBBBAABAAAAAABAAAAAABBABBABABAAABAAABAAAAABABAABABAABBBAAAABABBABAAABBBABAABBAABBBAABABBBABBBBBAAAABBAAABBBABBABBBAAABAABABABBABABABABBBAABABABAABBBBBAABAABBABAABABBBBBAABBAABABBAAABAAABABBBABABBBBAAABAABBBAABAABABBAABABAAAAABBBBAABABBBBBBABBBBBABBBABABBBAAAAAAABBAABAAAABAAAABBAABAABAABAABBBABBBAB...

output:

YES
1 2 3 7 8 10 11 16 17 18 19 23 24 26 27 29 30 31 32 33 35 36 37 38 40 41 45 47 48 50 51 53 54 58 62 64 66 67 68 69 71 72 74 76 78 80 82 85 86 87 88 89 92 93 94 95 96 98 99 102 104 105 107 108 109 111 112 114 117 118 119 121 123 124 125 126 127 129 130 132 133 134 135 136 137 139 140 141 142 143 ...

result:

ok good solution

Test #8:

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

input:

AABABBAAAAABBAAAAABBBAAAAABBAABBBBBABBABABBAAAABAAABAABAAABBABBABBABAABBBBBBBAABABBBBBAAABABABABBBAABABABAAAAABBAABAABAABABABABBAABBBAABAABBAAAABBBBBBBBABBBBABAAAABAABBABABAAABABABBBAAABAAAABBBAAABBBAAABABBBAAABBBAAABBBBABAABAAABABAABABBAAAABBBAAABBBAABAAABABABBBBAABBABABBBBAAABAABBBBABBAABBBAAAABAA...

output:

NO

result:

ok no solution

Test #9:

score: -100
Wrong Answer
time: 0ms
memory: 5292kb

input:

BBAAAAAABAAABBBAABABABAABABAAABABAAAAABBBAAAABBABBABAAABABAAAABBAABBBBBBBAABABABBBBABBABAABBBABAAAABBABABBBAABBAABBBABBABBAABBBAAABBABABAAAAAABBBABBBAABAAAABAAAABAAABAAAAAAABAAAAABBABBBAAAAABBBAAABBBABBBBBAAABBAABAAABAAABBBAABBABBAABAAABBAAABAAAAABAAABBBABAAABABAAAAAAAABBBAAAAAABAAABAAABBABABBABABBA...

output:

NO

result:

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