QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #393611 | #850. Edit Distance Yet Again | fantis | WA | 362ms | 45004kb | C++14 | 2.4kb | 2024-04-18 21:36:33 | 2024-04-18 21:36:33 |
Judging History
answer
#include<bits/stdc++.h>//0xnnb
using namespace std;
typedef long long ll;
typedef double db;
int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
typedef unsigned long long ull;
const int N=1000005,K=1005;
const ull P=99997;
int T,n,m,k,dp[K][K*2],pre[K][K*2],ans;
char a[N],b[N];
ull power[N],hasha[N],hashb[N];
void gethash(){
for(int i=1;i<=n;i++){
hasha[i]=hasha[i-1]*P+(a[i]-'a');
}
for(int i=1;i<=m;i++){
hashb[i]=hashb[i-1]*P+(b[i]-'a');
}
}
bool check(int la,int lb,int len){
ull xa=hasha[la+len]-hasha[la]*power[len];
ull xb=hashb[lb+len]-hashb[lb]*power[len];
return xa==xb;
}
int erfen(int la,int lb){
int l=0,r=min(n-la,m-lb),ans=l;
while(l<=r){
int mid=(l+r)>>1;
if(check(la,lb,mid)){
ans=mid,l=mid+1;
}
else r=mid-1;
}
return ans;
}
void solve(int x,int y){
if(!x)return;
int yy=pre[x][y+k];
solve(x-1,yy);
int pos=dp[x-1][yy+k]+yy;
if(y>yy){
printf("INSERT %d %c\n",pos+1,b[pos+1]);
}
else if(y<yy){
printf("DELETE %d\n",pos+1);
}
else{
printf("REPLACE %d %c\n",pos+1,b[pos+1]);
}
}
int main(){
power[0]=1;
for(int i=1;i<=1000000;i++){
power[i]=power[i-1]*P;
}
T=read();
for(int TT=1;TT<=T;TT++){
n=read(),m=read(),k=read();
scanf("%s%s",a+1,b+1);
if(abs(n-m)>k){
printf("NO\n");
continue;
}
gethash();
for(int i=0;i<=k;i++){
for(int j=-k;j<=k;j++){
dp[i][j+k]=-1;
}
}
dp[0][k]=0;
ans=-1;
for(int i=0;i<=k;i++){
for(int j=-k;j<=k;j++){
if(dp[i][j+k]==-1)continue;
int tmp=dp[i][j+k];
dp[i][j+k]=tmp+erfen(tmp,tmp+j);
tmp=dp[i][j+k];
if(i==k)continue;
if(j!=k&&tmp+j+1<=m){
if(tmp>dp[i+1][j+1+k]){
dp[i+1][j+1+k]=tmp;
pre[i+1][j+1+k]=j;
}
}
if(j!=-k&&tmp+1<=n){
if(tmp+1>dp[i+1][j-1+k]){
dp[i+1][j-1+k]=tmp+1;
pre[i+1][j-1+k]=j;
}
}
if(tmp+1<=n&&tmp+j+1<=m){
if(tmp+1>dp[i+1][j+k]){
dp[i+1][j+k]=tmp+1;
pre[i+1][j+k]=j;
}
}
}
if(dp[i][m-n+k]==n){
ans=i;
break;
}
}
if(ans==-1){
printf("NO\n");
continue;
}
printf("YES\n%d\n",ans);
solve(ans,m-n);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 18272kb
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: 20308kb
input:
100 100 100 0 mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm 16 7 100 vvvvvvvvvvvvvvvv qydopaq 37 33 43 ggggggggggggggggggggggggggggggggggggg osk...
output:
YES 0 YES 16 DELETE 1 DELETE 1 DELETE 1 DELETE 1 DELETE 1 DELETE 1 DELETE 1 DELETE 1 DELETE 1 REPLACE 1 q REPLACE 2 y REPLACE 3 d REPLACE 4 o REPLACE 5 p REPLACE 6 a REPLACE 7 q 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: 224ms
memory: 30420kb
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: 301ms
memory: 44932kb
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: 362ms
memory: 44984kb
input:
5 999000 998971 1000 lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
output:
NO NO NO NO NO
result:
ok OK!
Test #6:
score: -100
Wrong Answer
time: 94ms
memory: 45004kb
input:
5 1000000 1000000 1000 faafaffaaffafaafaffafaaffaafaffaaffafaaffaafaffafaafaffaaffafaafaffafaaffaafaffafaafaffaaffafaaffaafaffaaffafaafaffafaaffaafaffaaffafaaffaafaffafaafaffaaffafaaffaafaffaaffafaafaffafaaffaafaffafaafaffaaffafaafaffafaaffaafaffaaffafaaffaafaffafaafaffaaffafaafaffafaaffaafaffafaafa...
output:
YES 0 YES 779 DELETE 1 DELETE 1 INSERT 2 l REPLACE 4 j REPLACE 5 d REPLACE 6 v REPLACE 8 t REPLACE 10 i REPLACE 11 b REPLACE 12 w REPLACE 13 o DELETE 15 DELETE 16 REPLACE 16 c REPLACE 18 n REPLACE 19 m INSERT 20 d REPLACE 22 m INSERT 23 x REPLACE 26 x REPLACE 27 w REPLACE 28 n REPLACE 29 y DELETE 31...
result:
wrong answer At test 0 expected 246 got 0