QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#432002 | #850. Edit Distance Yet Again | Made_in_Code | RE | 880ms | 47548kb | C++14 | 2.4kb | 2024-06-06 15:49:13 | 2024-06-06 15:49:14 |
Judging History
answer
#include <iostream>
#define ULL unsigned long long
using namespace std;
const int kMaxN = 1e5 + 1, kMaxM = 1001;
const int kInf = 1e9, kBase = 15553;
int o, n, m, k, f[kMaxN << 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 + kMaxN][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 + kMaxN][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 + kMaxN][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], f[i + kMaxN][0] = -i;
}
for (int i = 1; i <= m; i++) {
ht[i] = ht[i - 1] * kBase + t[i], f[-i + kMaxN][0] = 0;
}
for (int &i = f[kMaxN][0] = 0; i < n && i < m && s[i + 1] == t[i + 1]; i++) {
}
for (int x = 1; x <= k; x++) {
for (int i = -m; i <= n; i++) {
int &p = f[i + kMaxN][x];
p = f[i + kMaxN][x - 1] + 1;
if (i > -m) {
p = max(p, f[i - 1 + kMaxN][x - 1]);
}
if (i < n) {
p = max(p, min(f[i + 1 + kMaxN][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: 1ms
memory: 8176kb
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: 8448kb
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: 880ms
memory: 47548kb
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: -100
Runtime Error
input:
5 999000 998976 995 llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...