QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#245939 | #4669. Genetic Modifications | Nightmare07 | WA | 0ms | 9960kb | C++14 | 2.6kb | 2023-11-10 14:42:08 | 2023-11-10 14:42:08 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M = 2010;
const int K = 25;
int n, m, tmp;
int f[N], Pre[N], G[M][M], G_[N][K], c[N];
bool dp[M][M], dp_[N][K];
char a[N], b[N];
int Find(int x) {
if (f[x] != x) f[x] = Find(f[x]);
return f[x];
}
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 = 2; i <= n; i ++)
if (a[i - 1] == a[i]) {
int fx = Find(i - 1), fy = Find(i);
f[fy] = fx;
}
for (int i = 1; i <= n; i ++) {
if (i == 1) Pre[i] = 0;
else if (a[i - 1] == a[i]) Pre[i] = max(1, Find(i) - 1);
else Pre[i] = max(1, Find(i - 1) - 1);
}
if (n <= 2000) {
for (int i = 1; i <= n; i ++)
if (a[i] == b[1]) dp[i][1] = 1;
for (int j = 2; j <= m; j ++) {
int cnt = 0;
dp[1][j] = 0;
queue<int> q;
for (int i = 2; i <= n; i ++) {
if (dp[i - 1][j - 1]) q.push(i - 1);
if (a[i] == b[j]) {
if (q.size() && q.front() < Pre[i]) q.pop();
if (q.size()) dp[i][j] = 1, G[i][j] = q.front();
}
}
}
int Id = 0;
for (int i = 1; i <= n; i ++) {
if (dp[i][m]) {
Id = i;
break;
}
}
if (!Id) puts("NO");
else {
puts("YES");
stack<int> s;
for (int i = m; i >= 1; i --) {
s.push(Id);
Id = G[Id][i];
if (i == 1) break;
}
while (s.size()) {
printf("%d ", s.top());
s.pop();
}
}
return 0;
}
if (m <= 20) {
for (int i = 1; i <= n; i ++)
if (a[i] == b[1]) dp_[i][1] = 1;
for (int j = 2; j <= m; j ++) {
int cnt = 0;
dp_[1][j] = 0;
queue<int> q;
for (int i = 2; i <= n; i ++) {
if (dp_[i - 1][j - 1]) q.push(i - 1);
if (a[i] == b[j]) {
if (q.size() && q.front() < Pre[i]) q.pop();
if (q.size()) dp_[i][j] = 1, G_[i][j] = q.front();
}
}
}
int Id = 0;
for (int i = 1; i <= n; i ++) {
if (dp_[i][m]) {
Id = i;
break;
}
}
if (!Id) puts("NO");
else {
puts("YES");
stack<int> s;
for (int i = m; i >= 1; i --) {
s.push(Id);
Id = G_[Id][i];
if (i == 1) break;
}
while (s.size()) {
printf("%d ", s.top());
s.pop();
}
}
return 0;
}
c[1] = 1, tmp = 1;
for (int i = 2; i <= n; i ++)
if (a[i] != a[i - 1]) c[++ tmp] = i;
if (a[1] != b[1]) {
if (tmp - 1 >= m) {
puts("YES");
for (int i = 2; i <= m + 1; i ++) printf("%d ", c[i]);
}
else puts("NO");
}
else {
if (tmp >= m) {
puts("YES");
for (int i = 1; i <= m; i ++) printf("%d ", c[i]);
}
else puts("NO");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 9960kb
input:
BBAAABBAAABAAA BAAB
output:
YES 1 3 4 6
result:
wrong answer wrong solution [2]