QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#369138#850. Edit Distance Yet AgainPYD1WA 1545ms33708kbC++144.7kb2024-03-27 20:58:132024-03-27 20:58:14

Judging History

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

  • [2024-03-27 20:58:14]
  • 评测
  • 测评结果:WA
  • 用时:1545ms
  • 内存:33708kb
  • [2024-03-27 20:58:13]
  • 提交

answer

#include <set>
#include <map>
#include <list>
#include <queue>
#include <cmath>
#include <time.h>
#include <random>
#include <bitset>
#include <vector>
#include <cstdio>
#include <stdio.h>
#include <iomanip>
#include <assert.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define mk make_pair
#define fi first
#define se second

inline int read(){
	int t = 0,f = 1;
	register char c = getchar();
	while (c < 48 || c > 57) f = (c == '-') ? -1 : 1,c = getchar();
	while (c >= 48 && c <= 57) t = (t << 1) + (t << 3) + (c ^ 48),c = getchar();
	return f * t;
}

inline int reads(char *s){
	int t = 0;
	register char c = getchar();
	while (c < 'a' || c > 'z') c = getchar();
	while (c >= 'a' && c <= 'z') s[++t] = c,c = getchar();
	return t;
}

const int N = 1e6 + 10,K = 1000 + 10,P = 131,V = 26,M1 = 998244353,M2 = 1000000007;
int T,n,m,k,dp[K][K << 1],xxx,yyy;
char s[N],t[N];
ll shsh1[N],shsh2[N],thsh1[N],thsh2[N],pw1[N],pw2[N];
pair <int,int> fr[K][K << 1];

mt19937 myrand((int)time(0));

inline int rnd(int l,int r) {return myrand() % (r - l + 1) + l;}

inline ll chash(ll *hs,ll *pw,int l,int r,int mod){
	return (hs[r] - hs[l - 1] * pw[r - l + 1] % mod + mod) % mod;
}

void upd(int x,int y,int kk,int xx,int yy){
	if (x > n || y > m) return ;
	int l = 0,r = min(n - x,m - y);
	if (r && s[x + 1] != t[y + 1]) r = 0;
	while (l < r){
		int mid = (l + r + 1) >> 1;
		if (!mid || (chash(shsh1,pw1,x + 1,x + mid,M1) == chash(thsh1,pw1,y + 1,y + mid,M1) && chash(shsh2,pw2,x + 1,x + mid,M2) == chash(thsh2,pw2,y + 1,y + mid,M2))) l = mid;
		else r = mid - 1;
	}
	x += l,y += l;
	int i = kk,j = x - y + k;
	if (x > dp[i][j]){
		if (xx == -1) xxx = i,yyy = j;
		dp[i][j] = x,fr[i][j] = mk(xx,yy);
	}
}

int cnt = 0;

namespace chk{
	bool ok = 1;
	char s[N];
	int n;
	void replace(int i,char c){
		// if (i > n) ok = 0;
		// s[i] = c;
	}
	void del(int i){
		// if (i < 0 || i > n) ok = 0;
		// for (int p = i;p < n;p++) s[p] = s[p + 1];
		// --n;
	}
	void ins(int i,char c){
		// if (i < 0 || i > n + 1) ok = 0;
		// for (int p = n;p >= i;p--) s[p + 1] = s[p];
		// s[i] = c;
		// ++n;
	}
}

void out(int x,int y){
	if (x == xxx && y == yyy) return ;
	if (fr[x][y].fi == -1) return ;
	int xx = fr[x][y].fi,yy = fr[x][y].se;
	out(xx,yy);
	int i = dp[x][y],j = i - (y - k);
	int ii = dp[xx][yy],jj = ii - (yy - k);
	if (y == yy){
		printf("REPLACE %d %c\n",cnt + ii + 1,t[jj + 1]);
		chk::replace(cnt + ii + 1,t[jj + 1]);
	}
	if (y == yy - 1){
		printf("INSERT %d %c\n",cnt + ii + 1,t[jj + 1]);
		chk::ins(cnt + ii + 1,t[jj + 1]);
		++cnt;
	}
	if (y == yy + 1){
		printf("DELETE %d\n",cnt + ii + 1);
		chk::del(cnt + ii + 1);
		--cnt;
	}
}

void runchk(){
	bool f = 1;
	if (m != chk::n) f = 0;
	for (int i = 1;i <= m;i++) if (t[i] != chk::s[i]) f = 0;
	if (!f || !chk::ok){
		puts("WA!!!");
		printf("%d %d %d\n",n,m,k);
		for (int i = 1;i <= n;i++) putchar(s[i]);puts("");
		for (int i = 1;i <= m;i++) putchar(t[i]);puts("");
		exit(0);
	}
}

void solve(){
	cnt = 0;
	n = read(),m = read(),k = read();
	reads(s),reads(t);
	// for (int i = 1;i <= n;i++) s[i] = rnd(0,V) + 'a';
	// for (int i = 1;i <= m;i++) t[i] = rnd(0,V) + 'a';
	// for (int i = 1;i < P;i++) w[i] = i;
	// shuffle(w + 1,w + P,myrand);
	pw1[0] = pw2[0] = 1;
	for (int i = 1;i <= max(n,m);i++) pw1[i] = pw1[i - 1] * P % M1,pw2[i] = pw2[i - 1] * P % M2;
	auto ghash = [&](ll *hs,char *s,int n,int mod){
		for (int i = 1;i <= n;i++) hs[i] = (hs[i - 1] * P % mod + s[i] - 'a' + 1) % mod;
	};
	ghash(shsh1,s,n,M1),ghash(thsh1,t,m,M1);
	ghash(shsh2,s,n,M2),ghash(thsh2,t,m,M2);
	for (int i = 0;i <= k;i++) for (int j = 0;j <= (k << 1);j++) dp[i][j] = -1,fr[i][j] = mk(-1,-1);
	// dp[0][k] = 0;
	upd(0,0,0,-1,-1);
	for (int i = 0;i < k;i++){
		for (int j = 0;j <= (k << 1);j++){
			int x = dp[i][j],y = x - (j - k);
			if (x < 0 || y < 0) continue;
			upd(x + 1,y + 1,i + 1,i,j);
			upd(x,y + 1,i + 1,i,j);
			upd(x + 1,y,i + 1,i,j); 
		}
	}
	int j = n - m + k;
	bool f = 0;
	for (int i = 0;i <= k;i++) f |= (dp[i][j] == n);
	if (!f) {puts("NO");return ;}
	for (int i = 1;i <= n;i++) chk::s[i] = s[i];
	// chk::n = n; 
	// chk::ok = 1;
	puts("YES");
	for (int i = 0;i <= k;i++){
		if (dp[i][j] == n){
			printf("%d\n",i);
			out(i,j);
			// runchk();
			return ;
		}
	}
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	T = read();
	while (T--) solve();
	// n = m = 100,k = 50;
	// while (1) solve();
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 12156kb

input:

2
3 4 3
kot
plot
5 7 3
zycie
porazka

output:

YES
2
INSERT 1 p
REPLACE 2 l
NO

result:

ok OK!

Test #2:

score: 0
Accepted
time: 3ms
memory: 14484kb

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: -100
Wrong Answer
time: 1545ms
memory: 33708kb

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:

wrong answer At test 27 expected NO got YES