QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#181796 | #7234. Pencil of Wishing | PhantomThreshold | RE | 34ms | 35956kb | C++20 | 3.8kb | 2023-09-17 00:41:27 | 2023-09-17 00:41:28 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const int maxn = 1500;
string S,T,str;
int sn,tn,n;
int gos[maxn][maxn],gose[maxn][maxn],got[maxn][maxn],gote[maxn][maxn];
int mnlen[maxn];
struct SAM
{
int las,rt,tot;
int par[maxn],len[maxn],ri[maxn];
int son[maxn][28];
int newnode(int L)
{
++tot;
memset(son[tot],0,sizeof son[tot]);
par[tot]=0;
len[tot]=L;
return tot;
}
void init()
{
tot=0;
las=rt=newnode(0);
}
void extend(const int w,const int r)
{
int p=las;
int np=newnode(len[p]+1); ri[np]=r;
while(p && !son[p][w]) son[p][w]=np,p=par[p];
if(!p) par[np]=rt;
else
{
int q=son[p][w];
if(len[q]==len[p]+1) par[np]=q;
else
{
int nq=newnode(len[p]+1);
memcpy(son[nq],son[q],sizeof son[nq]);
par[nq]=par[q];
par[np]=par[q]=nq;
while(p&&son[p][w]==q) son[p][w]=nq,p=par[p];
}
}
las=np;
}
vector<int>V[maxn];
set<int>S[maxn];
void dfs(const int x)
{
if(ri[x]) S[x].insert(ri[x]);
for(auto y:V[x]) dfs(y);
for(auto y:V[x])
{
if(S[x].size()<S[y].size()) swap(S[x],S[y]);
for(auto it:S[y])
S[x].insert(it);
}
for(int i=0;i<=sn;i++)
{
auto it= S[x].lower_bound(i+mnlen[x]);
if(it==S[x].end() || *it>sn) gos[i][x]= -1;
else gos[i][x]= *it;
if(i+mnlen[x]<=sn)
{
it= S[x].find(sn);
if(it!=S[x].end()) gose[i][x]=1;
}
}
for(int i=0;i<=tn;i++)
{
auto it=S[x].lower_bound(sn+1+i+mnlen[x]);
if(it==S[x].end()) got[i][x]= -1;
else got[i][x]= (*it)-sn-1;
if(i+mnlen[x]<=tn)
{
it= S[x].find(sn+1+tn);
if(it!=S[x].end()) gote[i][x]=1;
}
}
}
void build()
{
for(int i=2;i<=tot;i++)
{
V[par[i]].push_back(i);
mnlen[i]= len[par[i]]+1;
}
dfs(rt);
}
}tr;
int f[maxn][maxn];
tuple<int,int,int>g[maxn][maxn];
signed main()
{
ios_base::sync_with_stdio(false); ////////////////////////////////////////
cin.tie(0);
cin>>S; sn=S.size();
cin>>T; tn=T.size();
str= S+(char)('z'+1)+T; n=str.size();
tr.init();
for(int i=0;i<n;i++)
tr.extend(str[i]-'a',i+1);
tr.build();
memset(f,-1,sizeof f);
f[0][0]=0;
for(int i=0;i<=sn;i++) for(int j=0;j<=tn;j++) if(f[i][j]!=-1)
{
for(int x=2;x<=tr.tot;x++) if(gos[i][x]!=-1)
{
if(tr.ri[x] && i==0)
{
int nexi=tr.ri[x], nexj=got[j][x];
if(nexj==-1||nexj!=tr.ri[x]) nexj=tn+1;
if(f[nexi][nexj]==-1 || f[nexi][nexj]>nexi)
{
f[nexi][nexj]=nexi;
g[nexi][nexj]= make_tuple( i,j,nexi );
}
}
int nexi=gos[i][x];
int nexj= got[j][x]==-1?tn+1:got[j][x];
int temp= f[i][j]+mnlen[x]+1;
if( (f[nexi][nexj]==-1 || f[nexi][nexj]>temp) && nexi!=sn )
{
f[nexi][nexj]=temp;
g[nexi][nexj]= make_tuple( i,j,mnlen[x] );
}
if(gose[i][x])
{
nexi=sn;
if(gote[j][x]) nexj=tn;
temp= f[i][j]+ mnlen[x]+1;
if( f[nexi][nexj]==-1 || f[nexi][nexj]>temp )
{
f[nexi][nexj]=temp;
g[nexi][nexj]= make_tuple( i,j,mnlen[x] );
}
}
}
}
int ansi,ansj,ans=sn+1;
for(int i=1;i<=sn;i++) if(f[i][tn+1]!=-1)
{
int j=tn+1;
int tc= f[i][j]+ (i!=sn);
if( tc<ans)
{
ans=tc;
ansi=i;
ansj=j;
}
}
for(int j=0;j<=tn+1;j++) if(f[sn][j]!=-1 && j!=tn)
{
int i=sn;
int tc= f[i][j];
if( tc<ans)
{
ans=tc;
ansi=i;
ansj=j;
}
}
int i=ansi,j=ansj;
vector<string>outp;
if(i!=sn) outp.emplace_back("*");
while(i!=0)
{
auto [pi,pj,len]= g[i][j];
outp.push_back( S.substr(i-len+1-1,len) );
if(pi+len!=i) outp.emplace_back("*");
i=pi,j=pj;
}
//cerr<<ans<<endl;
for(int k=(int)outp.size()-1;k>=0;k--) cout<<outp[k];
cout<<endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 8ms
memory: 22040kb
input:
aabb ab
output:
aa*
result:
ok correct
Test #2:
score: 0
Accepted
time: 1ms
memory: 21564kb
input:
abaabaaabbbaabbb abaabbbaabaaabbb
output:
abaaba*
result:
ok correct
Test #3:
score: 0
Accepted
time: 0ms
memory: 21940kb
input:
amuletofyendor amuletofshmendor
output:
*y*
result:
ok correct
Test #4:
score: 0
Accepted
time: 8ms
memory: 21744kb
input:
spbau spbsu
output:
*a*
result:
ok correct
Test #5:
score: 0
Accepted
time: 4ms
memory: 23040kb
input:
b abaabaaaabaababbabba
output:
b
result:
ok correct
Test #6:
score: 0
Accepted
time: 0ms
memory: 21840kb
input:
bbaabaaa babbaabbbbababbaaab
output:
*a
result:
ok correct
Test #7:
score: 0
Accepted
time: 1ms
memory: 21948kb
input:
abb baabababababbbb
output:
a*
result:
ok correct
Test #8:
score: 0
Accepted
time: 1ms
memory: 21440kb
input:
baaaaaaa abaabbbaabbbba
output:
b*
result:
ok correct
Test #9:
score: 0
Accepted
time: 34ms
memory: 34224kb
input:
aaabbababbbabaaaaabababaabaabbbbaaabbabbabbbaaaabaabaaabbbaabbaaaabbabbabaababbaabbbabaabababbabbbbbbababbaaabbababbaababaabbbbbababbaaaabaabbabaababbabbbbaaababbbabbabbaabb aabbbbbabbbaaababababaaaaabbbababbaaabababbbaabababbaabbaaabaaaabaaababaabaabbabaabaaaabbbaaababaabbbbbbbbaaaaaaaabbaaaaabbaab...
output:
*b
result:
ok correct
Test #10:
score: 0
Accepted
time: 8ms
memory: 31708kb
input:
bbaabaabbaaaabbbbabbaababababbbbababaaaa abaabbaabbaaabbbaabaababaaaababbbbbbababbbaabbbabbbbbabababaabbababaabbbbbbbbaaababababaaababababbbabaababababaabababbaaaaaaaabbaaabbaabbbbaaabbbbbaaaaaaaaabababaaababbbbabbbbaaabbaaaababbaaababbbaaababaaaaabbbbbabaaabaabababbababababbabbaababbbabbaabbbbbbbab...
output:
b*
result:
ok correct
Test #11:
score: 0
Accepted
time: 13ms
memory: 35956kb
input:
abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaab...
output:
*aabbabaaba*babbabaabbaababbab*abaababbaabbabaabb*
result:
ok correct
Test #12:
score: 0
Accepted
time: 1ms
memory: 23088kb
input:
aaaaaabbaaayxybbaaaaabbbb aaaaaabaaaayxybbaaaaaabbb
output:
*bbbb
result:
ok correct
Test #13:
score: 0
Accepted
time: 4ms
memory: 23592kb
input:
bbbbaaaaabbyxyaaabbaaaaaa bbbaaaaaabbyxyaaaabaaaaaa
output:
bbbb*
result:
ok correct
Test #14:
score: 0
Accepted
time: 8ms
memory: 32408kb
input:
bbbaabbbabaaabbbaababbabbbabbaaabbbbbaababb bbbbbabbabbaaabaabbbababbbabaabaabbbbabaaaaabbabbbabababaaabaabbbbaaaaabaaaaabaaaabbbbabbaabababbbbaaaaabbabaaaabbabbbbbbaaaaaabaaaabbaababbbabbbbbaabbbabbabaaaaababaabaabbabbbabbbbbbabbababaabbaaaabbaaabbaabaababababbaabbababbabbaabaabbabbbbaabbaabaabbaba...
output:
*bb
result:
ok correct
Test #15:
score: -100
Runtime Error
input:
baabaabaabbbbaaaaabaaababbabbbbbaaaaabbbabaaaabaababaabbbbbabbbbababaabbabbabbbbaaaabbabaaababaabbbaabbbabbabbabaabaaaabbaaabaaaaabaaaabbbbabaabbbaabbaaabbbbabaabaabababaabbbbabaaabbaaaaababaaaababbabababaabbabaaababbaaaaaaaababbbaabaaabababbbbbabbbbbabbbababbbaabbaaabaababbbbabaaaabbbabbbaaababaaba...