QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #85883 | #850. Edit Distance Yet Again | eyiigjkn | WA | 7ms | 12112kb | C++14 | 2.2kb | 2023-03-08 20:28:02 | 2023-03-08 20:28:06 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
using ll=long long;
using Hash=pair<int,int>;
constexpr int N=1e6,p1=1e9+7,p2=1e9+9,Base=998244353;
int n,m,K;
char s1[1000010],s2[1000010];
Hash pw[1000010],sum1[1000010],sum2[1000010];
struct Info
{
int v,x,y;
Info(){}
Info(int v,int x,int y):v(v),x(x),y(y){}
Info &operator+=(const Info &t)
{
if(v<t.v) *this=t;
return *this;
}
}f[1010][2010];
inline Hash operator+(const Hash &x,const Hash &y){return {(x.first+y.first)%p1,(x.second+y.second)%p2};}
inline Hash operator-(const Hash &x,const Hash &y){return {(x.first-y.first+p1)%p1,(x.second-y.second+p2)%p2};}
inline Hash operator*(const Hash &x,const Hash &y){return {(ll)x.first*y.first%p1,(ll)x.second*y.second%p2};}
inline Hash geths1(int l,int r){return sum1[r]-pw[r-l+1]*sum1[l-1];}
inline Hash geths2(int l,int r){return sum2[r]-pw[r-l+1]*sum2[l-1];}
int calc(int x,int y)
{
int l=0,r=min(n-x+1,m-y+1),mid;
while(l<r)
{
mid=(l+r+1)/2;
if(geths1(x,x+mid-1)==geths2(y,y+mid-1)) l=mid;
else r=mid-1;
}
return l;
}
void getans(int k,int x,int y)
{
printf("YES\n%d\n",k);
for(;k;k--)
{
Info t=f[k][y-x+K];
int tx=t.x,ty=tx+t.y;
if(y-x==ty-tx) printf("REPLACE %d %c\n",tx+1,s2[ty+1]);
else if(y-x==ty-tx-1) printf("DELETE %d\n",tx+1);
else printf("INSERT %d %c\n",tx+1,s2[ty+1]);
x=tx;y=ty;
}
}
int main()
{
int T;
cin>>T;
pw[0]={1,1};
for(int i=1;i<=N;i++) pw[i]=pw[i-1]*Hash{Base,Base};
while(T--)
{
bool ok=0;
scanf("%d%d%d%s%s",&n,&m,&K,s1+1,s2+1);
for(int i=1;i<=n;i++) sum1[i]=sum1[i-1]*Hash{Base,Base}+Hash{s1[i],s1[i]};
for(int i=1;i<=m;i++) sum2[i]=sum2[i-1]*Hash{Base,Base}+Hash{s2[i],s2[i]};
for(int i=0;i<=K;i++) fill(f[i],f[i]+2*K+1,Info(-1,0,0));
f[0][K]=Info(calc(1,1),0,0);
for(int i=0;i<K && !ok;i++)
for(int j=-K;j<=K;j++)
if(~f[i][j+K].v)
{
int x=f[i][j+K].v,y=x+j;
if(x==n && y==m)
{
ok=1;getans(i,x,y);
break;
}
if(x<n && y<m) f[i+1][j+K]+=Info(x+1+calc(x+2,y+2),i,j);
if(x<n && j>-K) f[i+1][j-1+K]+=Info(x+1+calc(x+2,y+1),i,j);
if(y<m && j<K) f[i+1][j+1+K]+=Info(x+calc(x+1,y+2),i,j);
}
if(!ok) puts("NO");
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 11484kb
input:
2 3 4 3 kot plot 5 7 3 zycie porazka
output:
YES 2 INSERT 2 l REPLACE 1 p NO
result:
ok OK!
Test #2:
score: -100
Wrong Answer
time: 7ms
memory: 12112kb
input:
100 100 100 0 mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm 16 7 100 vvvvvvvvvvvvvvvv qydopaq 37 33 43 ggggggggggggggggggggggggggggggggggggg osk...
output:
NO YES 16 REPLACE 16 q REPLACE 15 a REPLACE 14 p REPLACE 13 o REPLACE 12 d REPLACE 11 y REPLACE 10 q DELETE 9 DELETE 8 DELETE 7 DELETE 6 DELETE 5 DELETE 4 DELETE 3 DELETE 2 DELETE 1 YES 28 REPLACE 28 c REPLACE 27 o REPLACE 26 z REPLACE 25 g REPLACE 24 a REPLACE 23 f REPLACE 22 w REPLACE 21 a REPLACE...
result:
wrong answer At test 0 expected YES got NO