QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#401497#850. Edit Distance Yet AgainxuqinWA 7ms19368kbC++144.3kb2024-04-28 20:33:152024-04-28 20:33:15

Judging History

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

  • [2024-04-28 20:33:15]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:19368kb
  • [2024-04-28 20:33:15]
  • 提交

answer

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cassert>
#include<set>
#include<random>
#include<chrono>
#include<bitset>
#include<map>
#include<queue>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<string>
#define eb emplace_back

using namespace std;
const int maxn=1e6+10, maxm=1e6+10, inf=2e9+10;
const double eps=1e-10;
typedef long long LL;
typedef unsigned long long ULL;
const LL INF=4e18;
typedef pair<LL, int> pli;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
inline int read() {
	int x=0, f=1; char c=getchar();
	for(; c<'0'||c>'9'; c=getchar()) if(c=='-') f=0;
	for(; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
	return f?x:-x;
}
int P;
mt19937 rnd((unsigned)chrono::steady_clock::now().time_since_epoch().count());
inline int ksm(int x, int y) {
	int s=1;
	for(; y; y>>=1, x=1LL*x*x%P)
		if(y&1) s=1LL*s*x%P;
	return s;
}
inline int add(int x, int y) {x+=y; return x>=P?x-P:x;}
inline int del(int x, int y) {x-=y; return x<0?x+P:x;}
LL gcd(LL x, LL y) {return y?gcd(y, x%y):x;}

const int B1=1607, B2=1609, M1=1000010747, M2=1000010749;
int pw[3][maxn];
char s[maxn], t[maxn]; int n, m, k;
struct pj{
    int hsh[3][maxn];
    inline void init(int sz, char ss[maxn]) {
        for(int i=1; i<=sz; ++i)
            hsh[1][i]=(1LL*hsh[1][i-1]*B1%M1+ss[i]-'a'+1)%M1,
            hsh[2][i]=(1LL*hsh[2][i-1]*B2%M2+ss[i]-'a'+1)%M2;
    }
    inline pii gethsh(int l, int r) {
        return make_pair((hsh[1][r]-1ll*hsh[1][l-1]*pw[1][r-l+1]%M1+M1)%M1,
                        (hsh[2][r]-1ll*hsh[2][l-1]*pw[2][r-l+1]%M2+M2)%M2);
    }
} S, T;
inline int lcp(int p, int q) {//lcp(s[p, n] t[q, m])
    int l=0, r=min(n-p+1, m-q+1);
    while(l<r) {
        int mid=(l+r+1)>>1;
        if(S.gethsh(p, p+mid-1)==T.gethsh(q, q+mid-1)) l=mid; else r=mid-1;
    }
    return l;
}

int dp[1010][2020], f[2020];
int pr[1010][2020];
inline void sol() {
    n=read(), m=read(), k=read();
    scanf("%s", s+1); S.init(n, s);
    scanf("%s", t+1); T.init(m, t); 
    int M=1010;
    dp[0][M]=lcp(1, 1);//(x, x+i)  (n, n+(m-n))
    if(m==n&&dp[0][M]==n) return printf("YES\n0\n"), void();
    int ii=-1, jj=-1;
    for(int i=1; i<=k; ++i) {
        for(int j=M-i; j<=M+i; ++j) f[j]=-1;
        for(int j=M-(i-1); j<=M+(i-1); ++j) {
            int x=dp[i-1][j];
            if(x==-1) continue;
            int y=x+(j-M);
            //(x, y)->(x+1, y)
            if(x<n) {
                int nx=x+1, ny=y, d=lcp(nx+1, ny+1);
                nx+=d, ny+=d;
                if(nx>f[ny-nx+M]) {
                    f[ny-nx+M]=nx;
                    pr[i][ny-nx+M]=j;
                }
            }
            //(x, y)->(x, y+1)
            if(y<m) {
                int nx=x, ny=y+1, d=lcp(nx+1, ny+1);
                nx+=d, ny+=d;
                if(nx>f[ny-nx+M]) {
                    f[ny-nx+M]=nx;
                    pr[i][ny-nx+M]=j;
                }
            }
            //(x, y)->(x+1, y+1)
            if(x<n&&y<m) {
                int nx=x+1, ny=y+1, d=lcp(nx+1, ny+1);
                nx+=d, ny+=d;
                if(nx>f[ny-nx+M]) {
                    f[ny-nx+M]=nx;
                    pr[i][ny-nx+M]=j;
                }
            }
        }
     //   printf("th=%d\n", i);
        for(int j=M-i; j<=M+i; ++j) {
            dp[i][j]=f[j];
     //       if(f[j]!=-1) printf("(%d, %d)\n", f[j], f[j]+j-M);
        }
        //chk
        if(-i<=m-n&&m-n<=i&&dp[i][M+m-n]==n) {
            ii=i, jj=M+m-n; break;
        }
    }
    if(ii==-1) return puts("NO"), void();
    printf("YES\n%d\n", ii);
    return;
    while(ii>0) {
        int nw=dp[ii][jj], pre=pr[ii][jj];
     //   printf("pre=%d\n", pre-M);
        int p=dp[ii-1][pre];
        //(nw, nw+jj-M)
        //(p, p+pre-M)
        if(jj==pre) {
            printf("REPLACE %d %c\n", p+1, t[p+pre-M+1]);
        } else if(jj==pre+1) {
            printf("INSERT %d %c\n", p+1, t[p+pre-M+1]);
        } else if(jj==pre-1) {
            printf("DELETE %d\n", p+1);
        }
        --ii; jj=pre;
    }
}

int main() {
    pw[1][0]=pw[2][0]=1;
    for(int i=1; i<=1000000; ++i) 
        pw[1][i]=1LL*pw[1][i-1]*B1%M1, pw[2][i]=1LL*pw[2][i-1]*B2%M2;
    int T=read();
    while(T--) sol();
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 7ms
memory: 19368kb

input:

2
3 4 3
kot
plot
5 7 3
zycie
porazka

output:

YES
2
NO

result:

wrong answer Test 0: incorrect operation in output