QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#246301 | #4669. Genetic Modifications | Nightmare07 | WA | 1ms | 3724kb | C++14 | 1.7kb | 2023-11-10 18:48:51 | 2023-11-10 18:48:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int l[N], r[N], f[N];
char a[N], b[N];
int Find(int x) {
if (f[x] != x) f[x] = Find(f[x]);
return f[x];
}
bool check(int x, char c, int id) {
if (a[x + 1] == c) return true;
else if (Find(x + 1) != n) return true;
else return false;
}
int main() {
scanf("%s%s", a + 1, b + 1);
n = strlen(a + 1), m = strlen(b + 1);
for (int i = 1; i <= n; i ++) f[i] = i;
for (int i = n - 1; i >= 1; i --) {
int fx = Find(i), fy = Find(i + 1);
if (a[i] == a[i + 1]) f[fx] = fy;
}
if (a[1] == b[1]) {
l[1] = 1;
for (int i = 1; i <= n; i ++) {
if (a[i] == b[1]) r[1] = i;
else break;
}
}
else {
for (int i = 1; i <= n; i ++) {
if (a[i] == b[i]) {
l[1] = r[1] = i;
break;
}
}
if (!l[1]) {
puts("NO");
return 0;
}
}
for (int i = 2; i <= m; i ++) {
l[i] = l[i - 1];
while (l[i] < n && !check(l[i], b[i], i - 1)) {
while (l[i] + 1 <= n && a[l[i] + 1] != a[l[i - 1]]) l[i] ++;
l[i] ++;
}
if (l[i] >= n) {
puts("NO");
return 0;
}
r[i] = max(r[i - 1], l[i]);
if (a[l[i] + 1] == b[i]) l[i] ++;
else l[i] = Find(l[i] + 1) + 1;
while (r[i] + 1 <= n && check(r[i] + 1, a[i], i - 1)) {
if (r[i] + 1 <= n && a[r[i] + 1] != a[l[i - 1]]) break;
r[i] ++;
}
if (!check(r[i], a[i], i - 1)) {
puts("NO");
return 0;
}
if (a[r[i] + 1] == b[i]) r[i] = Find(r[i] + 1);
else r[i] = Find(r[i] + 1) + 1;
}
for (int i = r[m] + 2; i <= n; i ++)
if (a[i - 1] != a[i]) {
puts("NO");
return 0;
}
puts("YES");
for (int i = 1; i <= m; i ++) printf("%d ", r[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3608kb
input:
BBAAABBAAABAAA BAAB
output:
YES 2 5 8 11
result:
ok good solution
Test #2:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
ABABABABAB ABAB
output:
NO
result:
ok no solution
Test #3:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
BBAAAAABBAAAAAABBABAABBBBBAABBBAAABABBABABBBAAABBAAAABBBBBABAABBBAABBBBBBBABBABABBAAAABBAAAABAAAABBABAAAAAAABBBBAAAAAABAABABBAAAAABBBBAABABABAAAAABBBABABBAABABBBBAABAABBBBBABBABABBAAABBAAAABBBABBABAAAABBBAABAAABBBAAAAAAAAAAAAABABBAABBBBABABAABBBBABAABBAAABABBBBAAAAAAAABBAAAABBABABABBBAAABAABBABBAAAA...
output:
NO
result:
ok no solution
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 3660kb
input:
BABABAABABBABAAAAABAABBAAAAABABABBABABBBBBBBAAAAAAABAAAAABAABBABBABABBBABBBAAAABBBABABBAAAABBBAABBBBBBBAAAABAAAABBBBABBAABAABBBAABBBBABAABABBBBAABABBABBAABAABBBBBAAABBAABABBBBAABABBABAABAAAABBABABAABBBABBBBABABABABAAABBABABABABBABAABBBBABAABBABBBBABABBABBBBBAABBBBBAAABAABAAAABBBBBABBABABABBBBABBBABA...
output:
NO
result:
wrong answer you didn't find a solution but jury did