QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#432001#850. Edit Distance Yet AgainMade_in_CodeWA 564ms39472kbC++142.4kb2024-06-06 15:47:552024-06-06 15:47:55

Judging History

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

  • [2024-06-06 15:47:55]
  • 评测
  • 测评结果:WA
  • 用时:564ms
  • 内存:39472kb
  • [2024-06-06 15:47:55]
  • 提交

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