QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #393617 | #850. Edit Distance Yet Again | fantis | AC ✓ | 912ms | 45072kb | C++14 | 2.4kb | 2024-04-18 21:49:06 | 2024-04-18 21:49:07 |
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;
}
const int N=1000005,K=1005;
const ll mod=1e9+7,P=233;
int T,n,m,k,dp[K][K*2],pre[K][K*2],ans;
char a[N],b[N];
ll power[N],hasha[N],hashb[N];
void gethash(){
for(int i=1;i<=n;i++){
hasha[i]=(hasha[i-1]*P+(a[i]-'a'))%mod;
}
for(int i=1;i<=m;i++){
hashb[i]=(hashb[i-1]*P+(b[i]-'a'))%mod;
}
}
bool check(int la,int lb,int len){
ll xa=(hasha[la+len]-hasha[la]*power[len]%mod+mod)%mod;
ll xb=(hashb[lb+len]-hashb[lb]*power[len]%mod+mod)%mod;
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%mod;
}
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: 16212kb
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: 8ms
memory: 18232kb
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: 547ms
memory: 30884kb
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: 697ms
memory: 44984kb
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: 793ms
memory: 44936kb
input:
5 999000 998971 1000 lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
output:
NO NO NO NO NO
result:
ok OK!
Test #6:
score: 0
Accepted
time: 234ms
memory: 45036kb
input:
5 1000000 1000000 1000 faafaffaaffafaafaffafaaffaafaffaaffafaaffaafaffafaafaffaaffafaafaffafaaffaafaffafaafaffaaffafaaffaafaffaaffafaafaffafaaffaafaffaaffafaaffaafaffafaafaffaaffafaaffaafaffaaffafaafaffafaaffaafaffafaafaffaaffafaafaffafaaffaafaffaaffafaaffaafaffafaafaffaaffafaafaffafaaffaafaffafaafa...
output:
YES 246 INSERT 1 a REPLACE 3 f INSERT 7 a INSERT 13 a INSERT 15 f INSERT 25 a INSERT 27 f INSERT 29 f INSERT 31 a INSERT 49 a INSERT 51 f INSERT 53 f INSERT 55 a INSERT 57 f INSERT 59 a INSERT 61 a INSERT 63 f INSERT 97 a REPLACE 99 f INSERT 103 a DELETE 109 REPLACE 111 f DELETE 114 INSERT 129 f REP...
result:
ok OK!
Test #7:
score: 0
Accepted
time: 912ms
memory: 45072kb
input:
5 999900 999925 992 ejqwvowvntrtmokrfeqeybcvgsupftozhkdsyytrioxrzbahikexefgyhpwbcztcydqiibxukojvgedldgmjufkzwttpvftctkpajgpwiklfzrkjxzsltqdbfdyxqpswrrlkdbmwckbhbfpqqgnhcixcnmphjulyykqfvdrqsdskbxqlqvekhwmvzmtqannmxrjgqcpdpofmqozyicaiqjikqxkeolandjydgvtjhnzubpdtkxymaxffnopnnrpnedobnfljcvtqwmuxdctutidm...
output:
YES 938 DELETE 1984 DELETE 2243 INSERT 4441 b DELETE 5841 DELETE 6398 INSERT 6785 b REPLACE 6948 t INSERT 6988 g REPLACE 7101 b INSERT 7373 b DELETE 10782 INSERT 12028 g REPLACE 13721 g INSERT 14908 t DELETE 14925 INSERT 15582 b REPLACE 17831 b INSERT 19811 b DELETE 22361 REPLACE 22445 t INSERT 2508...
result:
ok OK!