QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#432002#850. Edit Distance Yet AgainMade_in_CodeRE 880ms47548kbC++142.4kb2024-06-06 15:49:132024-06-06 15:49:14

Judging History

你现在查看的是最新测评结果

  • [2024-06-06 15:49:14]
  • 评测
  • 测评结果:RE
  • 用时:880ms
  • 内存:47548kb
  • [2024-06-06 15:49:13]
  • 提交

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...

output:


result: