QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#373841 | #850. Edit Distance Yet Again | jijidawang | WA | 6ms | 12840kb | C++14 | 3.6kb | 2024-04-02 08:48:50 | 2024-04-02 08:48:51 |
Judging History
answer
#include <bits/stdc++.h>
namespace // my guiding star
{
#define filein(x) freopen(x".in", "r", stdin);
#define fileout(x) freopen(x, "w", stdout);
#define fileerr(x) freopen(x, "w", stderr);
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout);
#define files(x) freopen(x".in", "r", stdin), freopen(x".ans", "w", stdout);
using namespace std;
#define cT const T&
template<typename T>
inline T chkmin(T& x, cT y){if (x > y) x = y; return x;}
template<typename T>
inline T chkmax(T& x, cT y){if (x < y) x = y; return x;}
template <typename T>
inline bool inrange(cT x, cT l, cT r){return (l <= x) && (x <= r);}
template <typename T>
inline bool inrange(cT l, cT r, cT L, cT R){return (L <= l) && (r <= R);}
#undef cT
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef unsigned u32;
template <typename T>
using pr = pair<T, T>;
typedef pr<int> pii;
typedef pr<ll> pll;
typedef pr<db> pdd;
typedef complex<double> cp;
typedef vector<int> vi;
inline void YN(bool x){puts(x ? "Yes" : "No");}
}
const int N = 1e6 + 233, P1 = 1e9 + 7, P2 = 1e9 + 9, base = 998244353, K = 1005;
int n, m, k;
string s1, s2;
struct hash_t
{
int first, second;
inline hash_t operator + (const hash_t& rhs) const {return {(first + rhs.first) % P1, (second + rhs.second) % P2};}
inline hash_t operator - (const hash_t& rhs) const {return {((first - rhs.first) % P1 + P1) % P1, ((second - rhs.second) % P2 + P2) % P2};}
inline hash_t operator * (const hash_t& rhs){return {(int)1ll * first * rhs.first % P1, (int)1ll * second * rhs.second % P2};}
inline bool operator == (const hash_t& rhs) const {return (first == rhs.first) && (second == rhs.second);}
}pw[N], hsh1[N], hsh2[N];
inline hash_t hash1(int l, int r){return hsh1[r] - pw[r-l+1] * hsh1[l-1];}
inline hash_t hash2(int l, int r){return hsh2[r] - pw[r-l+1] * hsh2[l-1];}
struct info
{
int v, x, y;
info& operator += (const info& rhs){return (v < rhs.v) ? *this = rhs : *this;}
}dp[K][K << 1];
inline int lcp(int x, int y)
{
int l = 0, r = min(n-x+1, m-y+1);
while (l <= r)
{
int mid = (l + r) >> 1;
if (hash1(x, x+mid-1) == hash2(y, y+mid-1)) l = mid + 1;
else r = mid - 1;
}
return l - 1;
}
void print(int p, int x, int y)
{
printf("YES\n%d\n", p);
while (p)
{
info t = dp[p][y-x+k];
int tx = t.x, ty = t.y;
if (y - x == ty - tx) printf("REPLACE %d %c\n", tx+1, s2[ty+1]);
else if (y - x == ty - tx - 1) printf("DELETE %d\n", tx+1);
else printf("INSERT %d %c\n", tx+1, s2[ty+1]);
--p; x = tx; y = ty;
}
}
int main()
{
int T; scanf("%d", &T); pw[0] = {1, 1};
for (int i=1; i<N; i++) pw[i] = pw[i-1] * hash_t{base, base};
while (T--)
{
scanf("%d%d%d", &n, &m, &k);
cin >> s1 >> s2; s1 = "$" + s1; s2 = "$" + s2;
for (int i=1; i<=n; i++) hsh1[i] = hsh1[i-1] * hash_t{base, base} + hash_t{s1[i], s1[i]};
for (int i=1; i<=m; i++) hsh2[i] = hsh2[i-1] * hash_t{base, base} + hash_t{s2[i], s2[i]};
for (int i=0; i<=k; i++) fill(dp[i], dp[i]+2*k+1, info{-1, 0, 0});
bool ok = false; dp[0][k] = {lcp(1, 1), 0, 0};
for (int i=0; (i<=k)&&!ok; i++)
for (int j=-k; j<=k; j++)
{
if (!~dp[i][j+k].v) continue;
int x = dp[i][j+k].v, y = x + j;
if ((x == n) && (y == m)){ok = true; print(i, x, y); break;}
if ((i < k) && (x < n) && (y < m)) dp[i+1][j+k] += info{x+1+lcp(x+2,y+2), x, y};
if ((i < k) && (x < n) && (j > -k)) dp[i+1][j-1+k] += info{x+1+lcp(x+2,y+1), x, y};
if ((i < k) && (y < m) && (j < k)) dp[i+1][j+1+k] += info{x+lcp(x+1,y+2), x, y};
}
if (!ok) puts("NO");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 6ms
memory: 12840kb
input:
2 3 4 3 kot plot 5 7 3 zycie porazka
output:
YES 3 INSERT 3 o REPLACE 2 l REPLACE 1 p NO
result:
wrong answer At test 0 expected 2 got 3