QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #368172 | #850. Edit Distance Yet Again | Harry27182 | AC ✓ | 3039ms | 81656kb | C++14 | 4.2kb | 2024-03-26 21:27:25 | 2024-03-26 21:27:26 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int mod1=1000000007,mod2=1000000009,N=1000005,K=1005;
int hs1[N],hs2[N],ht1[N],ht2[N],p1[N],p2[N];char s[N],t[N];
vector<pair<int,int> >b[K],a[K];pair<int,int> val[K];
int n,m,k,T,vis[K<<1];
int qs1(int l,int r){return (hs1[r]-1ll*hs1[l-1]*p1[r-l+1]%mod1+mod1)%mod1;}
int qs2(int l,int r){return (hs2[r]-1ll*hs2[l-1]*p2[r-l+1]%mod2+mod2)%mod2;}
int qt1(int l,int r){return (ht1[r]-1ll*ht1[l-1]*p1[r-l+1]%mod1+mod1)%mod1;}
int qt2(int l,int r){return (ht2[r]-1ll*ht2[l-1]*p2[r-l+1]%mod2+mod2)%mod2;}
void print(int p,int q)
{
if(p==0)return;
for(int i=0;i<a[p-1].size();i++)
{
int x=0,y=0;
if(a[p-1][i].first<n)
{
x=a[p-1][i].first+1;y=a[p-1][i].second;
int l=1,r=min(n-x,m-y),pos=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(qs1(x+1,x+mid)==qt1(y+1,y+mid)&&qs2(x+1,x+mid)==qt2(y+1,y+mid))pos=mid,l=mid+1;
else r=mid-1;
}
if(a[p][q]==make_pair(x+pos,y+pos))
{
val[p]=make_pair(i,1);print(p-1,i);
return;
}
}
if(a[p-1][i].second<m)
{
x=a[p-1][i].first;y=a[p-1][i].second+1;
int l=1,r=min(n-x,m-y),pos=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(qs1(x+1,x+mid)==qt1(y+1,y+mid)&&qs2(x+1,x+mid)==qt2(y+1,y+mid))pos=mid,l=mid+1;
else r=mid-1;
}
if(a[p][q]==make_pair(x+pos,y+pos))
{
val[p]=make_pair(i,2);print(p-1,i);
return;
}
}
if(a[p-1][i].first<n&&a[p-1][i].second<m)
{
x=a[p-1][i].first+1;y=a[p-1][i].second+1;
int l=1,r=min(n-x,m-y),pos=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(qs1(x+1,x+mid)==qt1(y+1,y+mid)&&qs2(x+1,x+mid)==qt2(y+1,y+mid))pos=mid,l=mid+1;
else r=mid-1;
}
if(a[p][q]==make_pair(x+pos,y+pos))
{
val[p]=make_pair(i,3);print(p-1,i);
return;
}
}
}
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
cin>>T;
for(int _=1;_<=T;_++)
{
cin>>n>>m>>k;cin>>(s+1)>>(t+1);
p1[0]=p2[0]=1;
for(int i=1;i<=max(n,m);i++)
{
p1[i]=1ll*p1[i-1]*131%mod1;
p2[i]=1ll*p2[i-1]*131%mod2;
}
for(int i=1;i<=n;i++)
{
hs1[i]=(1ll*hs1[i-1]*131%mod1+s[i])%mod1;
hs2[i]=(1ll*hs2[i-1]*131%mod2+s[i])%mod2;
}
for(int i=1;i<=m;i++)
{
ht1[i]=(1ll*ht1[i-1]*131%mod1+t[i])%mod1;
ht2[i]=(1ll*ht2[i-1]*131%mod2+t[i])%mod2;
}
for(int i=0;i<=k;i++)a[i].clear(),b[i].clear(),a[i].shrink_to_fit(),b[i].shrink_to_fit();
b[0].emplace_back(make_pair(0,0));
int flag=0;
for(int i=0;i<=k;i++)
{
for(int j=0;j<b[i].size();j++)
{
int x=b[i][j].first,y=b[i][j].second;
int l=1,r=min(n-x,m-y),pos=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(qs1(x+1,x+mid)==qt1(y+1,y+mid)&&qs2(x+1,x+mid)==qt2(y+1,y+mid))pos=mid,l=mid+1;
else r=mid-1;
}
a[i].emplace_back(make_pair(x+pos,y+pos));
}
vector<pair<int,int> >tmp;
for(int j=-k;j<=k;j++)vis[j+k]=0;
sort(a[i].begin(),a[i].end());
for(int j=a[i].size()-1;j>=0;j--)
{
if(vis[a[i][j].first-a[i][j].second+k])continue;
vis[a[i][j].first-a[i][j].second+k]=1;
tmp.emplace_back(a[i][j]);
}
swap(tmp,a[i]);
for(int j=0;j<a[i].size();j++)
{
if(a[i][j].first==n&&a[i][j].second==m)
{
cout<<"YES\n";
cout<<i<<'\n';flag=1;
print(i,j);
int num1=a[0][0].first,num2=a[0][0].second;
for(int p=1;p<=i;p++)val[p].first=val[p+1].first;
for(int p=1;p<=i;p++)
{
int q=val[p].first,lq=val[p-1].first;
int now1=a[p][q].first-a[p-1][lq].first,now2=a[p][q].second-a[p-1][lq].second;
if(val[p].second==1)cout<<"DELETE "<<num1+1<<'\n',now1--;
else if(val[p].second==2)cout<<"INSERT "<<num1+1<<' '<<t[a[p-1][lq].second+1]<<'\n',now1++;
else cout<<"REPLACE "<<num1+1<<' '<<t[a[p-1][lq].second+1]<<'\n';
num1+=now1;num2+=now2;
}
break;
}
}
if(flag==1)break;
for(int j=0;j<a[i].size();j++)
{
if(a[i][j].first<n)b[i+1].emplace_back(make_pair(a[i][j].first+1,a[i][j].second));
if(a[i][j].second<m)b[i+1].emplace_back(make_pair(a[i][j].first,a[i][j].second+1));
if(a[i][j].first<n&&a[i][j].second<m)b[i+1].emplace_back(make_pair(a[i][j].first+1,a[i][j].second+1));
}
}
if(flag==0)cout<<"NO\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7800kb
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: 4ms
memory: 8024kb
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: 0
Accepted
time: 2589ms
memory: 45712kb
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: 2448ms
memory: 70240kb
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: 3039ms
memory: 81656kb
input:
5 999000 998971 1000 lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
output:
NO NO NO NO NO
result:
ok OK!
Test #6:
score: 0
Accepted
time: 823ms
memory: 55456kb
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: 2254ms
memory: 80340kb
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!