QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#743103 | #7955. Tandem Copy | yuto1115# | WA | 0ms | 3852kb | C++20 | 1.9kb | 2024-11-13 18:14:32 | 2024-11-13 18:14:39 |
Judging History
answer
#include <cstdio>
#include <vector>
#include <cstring>
struct block {
char x, y;
int len, end;
};
const int N = 20005;
char s[N], t[N];
int n, m, t_block[N], s_block[N], dp[N];
std::vector<block> ss, tt;
void decomp(char *s, int n, int *s_block, std::vector<block> &blocks) {
for (int i = 0; i + 1 < n;) {
blocks.push_back({s[i], s[i + 1], 0});
++i;
int len = 1;
do {
s_block[i - 1] = blocks.size() - 1;
++len;
++i;
} while (i < n && s[i] == s[i - 2]);
blocks.back().len = len;
blocks.back().end = i;
--i;
}
}
int main() {
scanf("%s%s", s, t);
n = strlen(s);
for (int i = 0; t[i]; ++m) {
t[m] = t[i];
do {
++i;
} while (t[i] == t[i - 1]);
}
t[m] = 0;
decomp(s, n, s_block, ss);
decomp(t, m, t_block, tt);
dp[0] = -1;
int ans = 0;
if (n == 1) {
if (tt.empty() && t[0] == s[0]) printf("1\n");
else printf("0\n");
return 0;
}
for (int i = 0; i < n; ++i) {
bool ok = 1;
int j, k;
dp[i] = dp[i - 1];
if (tt.empty()) {
if (s[i] == t[0]) dp[i] = i;
} else if (i == 0) {
continue;
}
else if (tt.size() == 1) {
if ((tt.back().x != s[i - 1] || tt.back().y != s[i]) && (tt.back().y != s[i - 1] || tt.back().x != s[i])) continue;
dp[i] = i - 1;
} else {
if (i == 1 || s[i] != s[i - 2]) {
if (tt.back().x != s[i - 1] || tt.back().y != s[i]) continue;
if (tt.size() > 1 && (i == 1)) continue;
if (s_block[i - 2] < (int)tt.size() - 2) continue;
for (j = (int)tt.size() - 2, k = s_block[i - 2]; j > 0 && ok; --j, --k) {
if (tt[j].x != ss[k].x || tt[j].y != ss[k].y) ok = 0;
if (tt[j].len < ss[k].len || (tt[j].len ^ ss[k].len) & 1) ok = 0;
}
if (ok) {
if (s[ss[k].end - 1] != t[tt[0].end - 1] && s[ss[k].end - 2] != t[tt[0].end - 2]) ok = 0;
}
} else ok = 0;
if (ok) {
dp[i] = ss[k].end - 2;
}
}
}
for (int i = 0; i < n; ++i) ans += dp[i] + 1;
printf("%d\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3852kb
input:
ACGCG CCG
output:
11
result:
wrong answer 1st lines differ - expected: '9', found: '11'