QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#246353 | #4669. Genetic Modifications | Nightmare07 | WA | 2ms | 3904kb | C++14 | 1.8kb | 2023-11-10 19:20:11 | 2023-11-10 19:20:12 |
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) {
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[1]) {
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])) {
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;
}
if (a[l[i] + 1] == b[i]) l[i] ++;
else l[i] = Find(l[i] + 1) + 1;
int L = l[i - 1], R = r[i - 1];
while (L < R) {
int mid = L + R + 1 >> 1;
if (check(mid, b[i])) L = mid;
else R = mid - 1;
}
r[i] = L;
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;
}
int lastans = n + 1;
stack<int> s;
for (int i = m; i >= 1; i --) {
lastans --;
if (lastans < l[i]) {
puts("NO");
return 0;
}
while (lastans < r[i] || a[r[i]] != b[i]) r[i] --;
s.push(r[i]);
lastans = r[i];
}
puts("YES");
while (s.size()) {
printf("%d ", s.top());
s.pop();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3664kb
input:
BBAAABBAAABAAA BAAB
output:
YES 2 5 8 11
result:
ok good solution
Test #2:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
ABABABABAB ABAB
output:
NO
result:
ok no solution
Test #3:
score: 0
Accepted
time: 2ms
memory: 3904kb
input:
BBAAAAABBAAAAAABBABAABBBBBAABBBAAABABBABABBBAAABBAAAABBBBBABAABBBAABBBBBBBABBABABBAAAABBAAAABAAAABBABAAAAAAABBBBAAAAAABAABABBAAAAABBBBAABABABAAAAABBBABABBAABABBBBAABAABBBBBABBABABBAAABBAAAABBBABBABAAAABBBAABAAABBBAAAAAAAAAAAAABABBAABBBBABABAABBBBABAABBAAABABBBBAAAAAAAABBAAAABBABABABBBAAABAABBABBAAAA...
output:
NO
result:
ok no solution
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3624kb
input:
BABABAABABBABAAAAABAABBAAAAABABABBABABBBBBBBAAAAAAABAAAAABAABBABBABABBBABBBAAAABBBABABBAAAABBBAABBBBBBBAAAABAAAABBBBABBAABAABBBAABBBBABAABABBBBAABABBABBAABAABBBBBAAABBAABABBBBAABABBABAABAAAABBABABAABBBABBBBABABABABAAABBABABABABBABAABBBBABAABBABBBBABABBABBBBBAABBBBBAAABAABAAAABBBBBABBABABABBBBABBBABA...
output:
NO
result:
wrong answer you didn't find a solution but jury did