QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#432001 | #850. Edit Distance Yet Again | Made_in_Code | WA | 564ms | 39472kb | C++14 | 2.4kb | 2024-06-06 15:47:55 | 2024-06-06 15:47:55 |
Judging History
answer
#include <iostream>
#define ULL unsigned long long
using namespace std;
const int kMaxN = 1e6 + 1, kMaxM = 1001;
const int kInf = 1e9, kBase = 15553;
int o, n, m, k, f[kMaxM << 1][kMaxM];
ULL hs[kMaxN], ht[kMaxN], pw[kMaxN];
string s, t;
void Max(int &x, int y) { x = max(x, y); }
int W() {
for (int i = 0; i <= k; i++) {
if (f[n - m + kMaxM][i] == m) {
cout << "YES\n"
<< i << '\n';
return i;
}
}
cout << "NO\n";
return 0;
}
int Print(int n, int m, int x) {
if (x <= 0) {
return n + 1;
} else if (f[n - m + 1 + kMaxM][x - 1] >= m - 1) {
int w = Print(n, m - 1, x - 1);
cout << "INSERT " << w << ' ' << t[m] << '\n';
return w + 1;
} else if (f[n - m - 1 + kMaxM][x - 1] >= m) {
int w = Print(n - 1, m, x - 1);
cout << "DELETE " << w << '\n';
return w;
} else if (s[n] != t[m]) {
int w = Print(n - 1, m - 1, x - 1);
cout << "REPLACE " << w << ' ' << t[m] << '\n';
return w + 1;
}
return Print(n - 1, m - 1, x) + 1;
}
int main() {
cin.tie(0), cout.tie(0);
ios::sync_with_stdio(0);
pw[0] = 1;
for (int i = 1; i < kMaxN; i++) {
pw[i] = pw[i - 1] * kBase;
}
cin >> o;
while (o--) {
cin >> n >> m >> k >> s >> t;
if (abs(n - m) > k) {
cout << "NO\n";
continue;
}
s = '~' + s, t = '~' + t;
for (int i = 1; i <= n; i++) {
hs[i] = hs[i - 1] * kBase + s[i];
}
for (int i = 1; i <= m; i++) {
ht[i] = ht[i - 1] * kBase + t[i];
}
for (int i = max(-k, -m); i <= min(k, n); i++) {
f[i + kMaxM][0] = min(-i, 0);
}
for (int &i = f[kMaxM][0]; i < n && i < m && s[i + 1] == t[i + 1]; i++) {
}
for (int x = 1; x <= k; x++) {
for (int i = max(-k, -m); i <= min(k, n); i++) {
int &p = f[i + kMaxM][x];
p = f[i + kMaxM][x - 1] + 1;
if (i > max(-k, -m)) {
p = max(p, f[i - 1 + kMaxM][x - 1]);
}
if (i < min(k, n)) {
p = max(p, min(f[i + 1 + kMaxM][x - 1] + 1, m));
}
if (p >= max(-i, 0)) {
int l = p + 1, r = min(n - i, m);
while (l <= r) {
int mid = l + r >> 1;
ULL ws = hs[i + mid] - hs[i + p] * pw[mid - p];
ULL wt = ht[mid] - ht[p] * pw[mid - p];
ws == wt ? l = mid + 1 : r = mid - 1;
}
p = r;
}
}
}
Print(n, m, W());
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 14112kb
input:
2 3 4 3 kot plot 5 7 3 zycie porazka
output:
YES 2 REPLACE 1 p INSERT 2 l NO
result:
ok OK!
Test #2:
score: 0
Accepted
time: 0ms
memory: 13748kb
input:
100 100 100 0 mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm 16 7 100 vvvvvvvvvvvvvvvv qydopaq 37 33 43 ggggggggggggggggggggggggggggggggggggg osk...
output:
YES 0 YES 16 REPLACE 1 q REPLACE 2 y REPLACE 3 d REPLACE 4 o REPLACE 5 p REPLACE 6 a REPLACE 7 q DELETE 8 DELETE 8 DELETE 8 DELETE 8 DELETE 8 DELETE 8 DELETE 8 DELETE 8 DELETE 8 YES 28 REPLACE 1 o REPLACE 2 s REPLACE 3 k REPLACE 5 m REPLACE 6 l REPLACE 8 j REPLACE 9 t REPLACE 10 u REPLACE 11 a REPLA...
result:
ok OK!
Test #3:
score: 0
Accepted
time: 408ms
memory: 24936kb
input:
100 3211 3185 685 wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...
output:
YES 552 REPLACE 4 i REPLACE 16 b REPLACE 17 s REPLACE 20 u REPLACE 29 j REPLACE 31 b REPLACE 33 z REPLACE 39 l REPLACE 67 l REPLACE 68 s REPLACE 70 i REPLACE 73 p REPLACE 91 g REPLACE 101 x REPLACE 111 y REPLACE 113 x REPLACE 115 s REPLACE 117 f REPLACE 121 m REPLACE 123 a REPLACE 130 h REPLACE 132 ...
result:
ok OK!
Test #4:
score: 0
Accepted
time: 561ms
memory: 39472kb
input:
5 999000 998976 995 llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
output:
YES 894 REPLACE 1682 u REPLACE 2752 y REPLACE 2983 z REPLACE 4433 b REPLACE 7318 m REPLACE 8237 b REPLACE 8898 n REPLACE 9049 m REPLACE 9504 n REPLACE 9903 n REPLACE 13572 q REPLACE 14221 v REPLACE 14615 y REPLACE 16903 j REPLACE 17197 e REPLACE 18073 v REPLACE 19408 b REPLACE 20512 p REPLACE 21033 ...
result:
ok OK!
Test #5:
score: 0
Accepted
time: 564ms
memory: 38440kb
input:
5 999000 998971 1000 lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
output:
NO NO NO NO NO
result:
ok OK!
Test #6:
score: -100
Wrong Answer
time: 128ms
memory: 39436kb
input:
5 1000000 1000000 1000 faafaffaaffafaafaffafaaffaafaffaaffafaaffaafaffafaafaffaaffafaafaffafaaffaafaffafaafaffaaffafaaffaafaffaaffafaafaffafaaffaafaffaaffafaaffaafaffafaafaffaaffafaaffaafaffaaffafaafaffafaaffaafaffafaafaffaaffafaafaffafaaffaafaffaaffafaaffaafaffafaafaffaaffafaafaffafaaffaafaffafaafa...
output:
YES 82 REPLACE 1967 a REPLACE 1968 f REPLACE 1969 a REPLACE 1970 f REPLACE 1971 f REPLACE 1972 a REPLACE 1973 f REPLACE 1974 a REPLACE 1975 a REPLACE 1976 f REPLACE 1977 f REPLACE 1978 a REPLACE 1979 a REPLACE 1980 f REPLACE 1981 a REPLACE 1982 f REPLACE 1983 f REPLACE 1984 a REPLACE 1985 f REPLACE ...
result:
wrong answer At test 0 expected 246 got 82