QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#246162 | #4669. Genetic Modifications | MYFJCHC | WA | 1ms | 4088kb | C++14 | 1.1kb | 2023-11-10 16:46:36 | 2023-11-10 16:46:37 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m;
char s[N], t[N];
int nxt[N], f[N], g[N];
int main()
{
scanf("%s%s", s + 1, t + 1);
n = strlen(s + 1), m = strlen(t + 1);
for(int i = 1; i <= n; i ++ ) nxt[i] = s[i] == s[i - 1] ? nxt[i - 1] : i - 1;
// for(int i = 1; i <= n; i ++ ) printf("%d ", nxt[i]);
// puts("");
g[m + 1] = n + 1;
for(int i = m, j = n; i > 0 && j > 0; i -- , j -- )
{
if(t[i] != s[j]) j = nxt[j];
else j = nxt[j] + 1;
if(j > 0) g[i] = j;
}
if(g[1] && nxt[g[1] - 1] == 0)
{
puts("YES");
for(int k = 1; k <= m; k ++ ) printf("%d ", g[k]);
return 0;
}
for(int i = 1, j = 1; i <= m && j <= n; i ++ , j ++ )
{
while(j <= m && t[i] != s[j]) j ++ ;
f[i] = j;
if(j <= m && g[j + 1] && nxt[g[j + 1] - 1] <= j)
{
puts("YES");
for(int k = 1; k <= i; k ++ ) printf("%d ", f[k]);
for(int k = i + 1; k <= m; k ++ ) printf("%d ", g[k]);
return 0;
}
}
// for(int i = 1; i <= m; i ++ ) printf("%d ", f[i]);
// puts("");
// for(int i = 1; i <= m; i ++ ) printf("%d ", g[i]);
// puts("");
puts("NO");
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3876kb
input:
BBAAABBAAABAAA BAAB
output:
YES 2 5 8 11
result:
ok good solution
Test #2:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
ABABABABAB ABAB
output:
NO
result:
ok no solution
Test #3:
score: 0
Accepted
time: 1ms
memory: 3884kb
input:
BBAAAAABBAAAAAABBABAABBBBBAABBBAAABABBABABBBAAABBAAAABBBBBABAABBBAABBBBBBBABBABABBAAAABBAAAABAAAABBABAAAAAAABBBBAAAAAABAABABBAAAAABBBBAABABABAAAAABBBABABBAABABBBBAABAABBBBBABBABABBAAABBAAAABBBABBABAAAABBBAABAAABBBAAAAAAAAAAAAABABBAABBBBABABAABBBBABAABBAAABABBBBAAAAAAAABBAAAABBABABABBBAAABAABBABBAAAA...
output:
NO
result:
ok no solution
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 4088kb
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:
wrong answer Integer 0 violates the range [1, 13058]