QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#64169 | #4669. Genetic Modifications | zimindaada | WA | 10ms | 4532kb | C++14 | 1.3kb | 2022-11-24 11:00:27 | 2022-11-24 11:00:28 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
namespace ztd{
using namespace std;
typedef long long ll;
template<typename T> inline T read(T& t) {
t=0;short f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
while (ch>='0'&&ch<='9') t=t*10+ch-'0',ch=getchar();
t*=f; return t;
}
}
using namespace ztd;
const int maxn = 1e5+7;
char s[maxn], t[maxn];
int n, m, o, p, pos[maxn], inbl[maxn];
struct node{int l, r;} a[maxn];
inline void NO(){
puts("NO");
exit(0);
}
inline void YES(){
puts("YES");
for(int i = 1; i <= m; ++i) cout << pos[i] << ' ';
exit(0);
}
signed main(){
scanf("%s\n%s",s+1,t+1);
n = strlen(s+1); m = strlen(t+1);
for(int i = 1; i <= n; ++i){
int cnt = 1, j;
for(j = i; j <= n; ++j){
if(j == n || s[j+1] != s[i]) break;
}
a[++o] = (node){i, j};
for(int p = i; p <= j; ++p) inbl[p] = o;
i = j;
}
for(int i = 1; i <= n; ++i){
if(s[i] == t[p+1]) pos[++p] = i;
}
if(p < m) NO();
pos[p+1] = n+1;
for(int i = m; i >= 1; --i){
if(inbl[pos[i]+1] >= inbl[pos[i+1]-1]) YES();
pos[i] = a[inbl[pos[i+1]-1]].l;
if(s[pos[i]] != t[i]) --pos[i];
}
if(inbl[pos[1]] == 1) YES();
else NO();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3484kb
input:
BBAAABBAAABAAA BAAB
output:
YES 2 5 8 11
result:
ok good solution
Test #2:
score: 0
Accepted
time: 2ms
memory: 3560kb
input:
ABABABABAB ABAB
output:
NO
result:
ok no solution
Test #3:
score: 0
Accepted
time: 1ms
memory: 4000kb
input:
BBAAAAABBAAAAAABBABAABBBBBAABBBAAABABBABABBBAAABBAAAABBBBBABAABBBAABBBBBBBABBABABBAAAABBAAAABAAAABBABAAAAAAABBBBAAAAAABAABABBAAAAABBBBAABABABAAAAABBBABABBAABABBBBAABAABBBBBABBABABBAAABBAAAABBBABBABAAAABBBAABAAABBBAAAAAAAAAAAAABABBAABBBBABABAABBBBABAABBAAABABBBBAAAAAAAABBAAAABBABABABBBAAABAABBABBAAAA...
output:
NO
result:
ok no solution
Test #4:
score: 0
Accepted
time: 4ms
memory: 3720kb
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: 2ms
memory: 4160kb
input:
BAABBBBBBAAABABABAAAAABAABBAAABBAABBBAABABBBABBABBBABBBBABAABAAAAABBBBBBBABABABAABABAABAABBBBBBABABABABBABBBBAABAABBAAABABBAAAAAAABBAAAAAAAABAAABABBAAABABABBBABAAABBBAABAABBABBBBBBBBBABBBABBBABBAABAABBABABBBBAAAABABAABAABABBABBABBBBBAABABABBBBBABAABBABABAABBABAABABBBBABABBBBBBABBBABABBAAABBAAABBABBA...
output:
NO
result:
ok no solution
Test #6:
score: 0
Accepted
time: 2ms
memory: 4216kb
input:
BBAABBAAABBBBAAABABBBABBBAABABAABBBABABBBAABBBBBBABBBAABABBBAAAAABABBABAABBAABABAABBAAABBBABAABBBAABAABABABBBBAABBBBBBBBBBBABBABABABBABBAAAAAAABAABABAABBABBABABBBBBAABBABBAABAABBBABBABBAABBBAAABBAAABABBBBBAAAABBAAABBAABABBABAABBBBAABBBAAAAAABBBAAAAABBBAAAABAABAAABBBAAABABBBABBBBBBBBAABABBABBBABAABAA...
output:
NO
result:
ok no solution
Test #7:
score: 0
Accepted
time: 3ms
memory: 3584kb
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: 4532kb
input:
AABABBAAAAABBAAAAABBBAAAAABBAABBBBBABBABABBAAAABAAABAABAAABBABBABBABAABBBBBBBAABABBBBBAAABABABABBBAABABABAAAAABBAABAABAABABABABBAABBBAABAABBAAAABBBBBBBBABBBBABAAAABAABBABABAAABABABBBAAABAAAABBBAAABBBAAABABBBAAABBBAAABBBBABAABAAABABAABABBAAAABBBAAABBBAABAAABABABBBBAABBABABBBBAAABAABBBBABBAABBBAAAABAA...
output:
NO
result:
ok no solution
Test #9:
score: -100
Wrong Answer
time: 10ms
memory: 4288kb
input:
BBAAAAAABAAABBBAABABABAABABAAABABAAAAABBBAAAABBABBABAAABABAAAABBAABBBBBBBAABABABBBBABBABAABBBABAAAABBABABBBAABBAABBBABBABBAABBBAAABBABABAAAAAABBBABBBAABAAAABAAAABAAABAAAAAAABAAAAABBABBBAAAAABBBAAABBBABBBBBAAABBAABAAABAAABBBAABBABBAABAAABBAAABAAAAABAAABBBABAAABABAAAAAAAABBBAAAAAABAAABAAABBABABBABABBA...
output:
YES 1 3 4 5 6 7 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 26 27 28 29 30 31 32 34 35 36 39 40 41 42 43 44 46 47 49 51 52 53 54 55 56 57 58 59 60 61 62 63 65 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 87 88 89 90 91 92 93 94 95 96 97 100 101 102 103 104 105 106 108 110 111 114 115 ...
result:
wrong answer you selected 72073 multiple times