QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#246305 | #4669. Genetic Modifications | Judgelight | WA | 2ms | 5992kb | C++14 | 1.1kb | 2023-11-10 18:49:35 | 2023-11-10 18:49:35 |
Judging History
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=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;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3972kb
input:
BBAAABBAAABAAA BAAB
output:
YES 2 5 8 11
result:
ok good solution
Test #2:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
ABABABABAB ABAB
output:
NO
result:
ok no solution
Test #3:
score: 0
Accepted
time: 1ms
memory: 4716kb
input:
BBAAAAABBAAAAAABBABAABBBBBAABBBAAABABBABABBBAAABBAAAABBBBBABAABBBAABBBBBBBABBABABBAAAABBAAAABAAAABBABAAAAAAABBBBAAAAAABAABABBAAAAABBBBAABABABAAAAABBBABABBAABABBBBAABAABBBBBABBABABBAAABBAAAABBBABBABAAAABBBAABAAABBBAAAAAAAAAAAAABABBAABBBBABABAABBBBABAABBAAABABBBBAAAAAAAABBAAAABBABABABBBAAABAABBABBAAAA...
output:
NO
result:
ok no solution
Test #4:
score: 0
Accepted
time: 1ms
memory: 4192kb
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: 5208kb
input:
BAABBBBBBAAABABABAAAAABAABBAAABBAABBBAABABBBABBABBBABBBBABAABAAAAABBBBBBBABABABAABABAABAABBBBBBABABABABBABBBBAABAABBAAABABBAAAAAAABBAAAAAAAABAAABABBAAABABABBBABAAABBBAABAABBABBBBBBBBBABBBABBBABBAABAABBABABBBBAAAABABAABAABABBABBABBBBBAABABABBBBBABAABBABABAABBABAABABBBBABABBBBBBABBBABABBAAABBAAABBABBA...
output:
NO
result:
ok no solution
Test #6:
score: 0
Accepted
time: 1ms
memory: 5716kb
input:
BBAABBAAABBBBAAABABBBABBBAABABAABBBABABBBAABBBBBBABBBAABABBBAAAAABABBABAABBAABABAABBAAABBBABAABBBAABAABABABBBBAABBBBBBBBBBBABBABABABBABBAAAAAAABAABABAABBABBABABBBBBAABBABBAABAABBBABBABBAABBBAAABBAAABABBBBBAAAABBAAABBAABABBABAABBBBAABBBAAAAAABBBAAAAABBBAAAABAABAAABBBAAABABBBABBBBBBBBAABABBABBBABAABAA...
output:
NO
result:
ok no solution
Test #7:
score: 0
Accepted
time: 1ms
memory: 4188kb
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: 2ms
memory: 5796kb
input:
AABABBAAAAABBAAAAABBBAAAAABBAABBBBBABBABABBAAAABAAABAABAAABBABBABBABAABBBBBBBAABABBBBBAAABABABABBBAABABABAAAAABBAABAABAABABABABBAABBBAABAABBAAAABBBBBBBBABBBBABAAAABAABBABABAAABABABBBAAABAAAABBBAAABBBAAABABBBAAABBBAAABBBBABAABAAABABAABABBAAAABBBAAABBBAABAAABABABBBBAABBABABBBBAAABAABBBBABBAABBBAAAABAA...
output:
NO
result:
ok no solution
Test #9:
score: -100
Wrong Answer
time: 1ms
memory: 5992kb
input:
BBAAAAAABAAABBBAABABABAABABAAABABAAAAABBBAAAABBABBABAAABABAAAABBAABBBBBBBAABABABBBBABBABAABBBABAAAABBABABBBAABBAABBBABBABBAABBBAAABBABABAAAAAABBBABBBAABAAAABAAAABAAABAAAAAAABAAAAABBABBBAAAAABBBAAABBBABBBBBAAABBAABAAABAAABBBAABBABBAABAAABBAAABAAAAABAAABBBABAAABABAAAAAAAABBBAAAAAABAAABAAABBABABBABABBA...
output:
NO
result:
wrong answer you didn't find a solution but jury did