QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#246124 | #4669. Genetic Modifications | zqs | WA | 0ms | 1408kb | C++14 | 1.6kb | 2023-11-10 16:22:42 | 2023-11-10 16:22:43 |
Judging History
answer
#include <cstdio>
#include <cstring>
char S[100005], T[100005];
int p1[100005], p2[100005], nxt[100005][2], pre[100005][2], len1, len2, n, m;
int ans[100005], len;
int getmost(int k) {
if (!k) return len1 = 0;
len1 = 0, nxt[k + 1][0] = nxt[k + 1][1] = k + 1;
for (int i = k; i; -- i)
nxt[i][0] = nxt[i + 1][0], nxt[i][1] = nxt[i + 1][1], nxt[i][S[i] - '0'] = i;
int j = 0;
for (int i = 1; i <= k && j < m; ++ i) {
int p = nxt[i][T[j + 1] - '0'];
if (p <= k) ++ j, p1[++ len1] = i = p;
else break;
}
return len1;
}
int getleast(int k) {
if (k > n) return len2 = 0;
len2 = 0;
int now = m;
for (int i = n; i >= k; -- i) {
int j = i;
while (j > k && S[j - 1] == S[i]) -- j;
if (j != k && !now) return 1e9;
if (S[i] == T[now]) p2[++ len2] = i = j, -- now;
else if (j > k) p2[++ len2] = i = j - 1, -- now;
else break;
}
return len2;
}
bool check() {
ans[0] = 0, ans[len + 1] = n + 1;
for (int i = 0; i <= len; ++ i)
for (int j = ans[i] + 1; j < ans[i + 1]; ++ j)
if (S[j] != S[ans[i] + 1]) return false;
return true;
}
int main() {
scanf("%s%s", S + 1, T + 1), n = strlen(S + 1), m = strlen(T + 1);
if (getmost(n) < m || getleast(1) > m) return puts("NO"), 0;
int l = 0, r = n;
while (l < r) {
int mid = l + r >> 1;
if (getmost(mid) + getleast(mid + 1) >= m) r = mid;
else l = mid + 1;
}
if (getmost(l) + getleast(l + 1) != m) return puts("NO"), 0;
for (int i = 1; i <= len1; ++ i) ans[++ len] = p1[i];
while (len2) ans[++ len] = p2[len2 --];
if (check()) {
puts("YES");
for (int i = 1; i <= len; ++ i) printf("%d ", ans[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: 1408kb
input:
BBAAABBAAABAAA BAAB
output:
NO
result:
wrong answer you didn't find a solution but jury did