QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#708940 | #9522. A Simple String Problem | qzez# | AC ✓ | 746ms | 78456kb | C++14 | 2.8kb | 2024-11-04 09:54:22 | 2024-11-06 21:49:49 |
Judging History
你现在查看的是测评时间为 2024-11-06 21:49:49 的历史记录
- [2024-11-10 22:36:11]
- hack成功,自动添加数据
- (/hack/1163)
- [2024-11-06 21:48:00]
- hack成功,自动添加数据
- (/hack/1142)
- [2024-11-04 09:54:22]
- 提交
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5+10;
int n;
char a[2][N];
struct SA{
static const int N=::N*2,K=__lg(N)+1;
char a[N];
int sa[N],rk[N],h[K][N];
void getsa(int n,int m=127){
static int old[N*2],id[N],p[N],cnt[N];
fill(old,old+1+n+n,0);
for(int i=1;i<=n;i++)cnt[rk[i]=a[i]]++;
for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
for(int i=n;i>=1;i--)sa[cnt[rk[i]]--]=i;
fill(cnt,cnt+1+m,0);
for(int len=1,k;len==1||m^n;len<<=1){
k=0;
for(int i=n-len+1;i<=n;i++)p[++k]=i;
for(int i=1;i<=n;i++)if(sa[i]>len)p[++k]=sa[i]-len;
for(int i=1;i<=n;i++)cnt[id[i]=rk[p[i]]]++;
for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
for(int i=n;i>=1;i--)sa[cnt[id[i]]--]=p[i];
copy(rk,rk+1+n,old),fill(cnt,cnt+1+m,0),m=0;
for(int i=1;i<=n;i++){
rk[sa[i]]=old[sa[i]]==old[sa[i-1]]&&old[sa[i]+len]==old[sa[i-1]+len]?m:++m;
}
}
for(int i=1,x=0;i<=n;i++){
for(x-=!!x;max(i,sa[rk[i]-1])+x<=n&&a[i+x]==a[sa[rk[i]-1]+x];x++);
h[0][rk[i]]=x;
}
for(int i=1;(1<<i)<=n;i++){
for(int j=1;j+(1<<i)-1<=n;j++){
h[i][j]=min(h[i-1][j],h[i-1][j+(1<<i-1)]);
}
}
}
int LCP(int l,int r){
if(l=rk[l],r=rk[r],l>r)swap(l,r);
int k=__lg(r-l++);
return min(h[k][l],h[k][r-(1<<k)+1]);
}
}A,B;
int LCP(int a,int b,int x,int y){
if(min(b,y)<1||max(b,y)>n)return 0;
return min({A.LCP(a*n+b,x*n+y),n-b+1,n-y+1});
}
int LCS(int a,int b,int x,int y){
if(min(b,y)<1||max(b,y)>n)return 0;
return min({B.LCP(n+n+1-(a*n+b),n+n+1-(x*n+y)),b,y});
}
int solve(int op){
for(int i=1;i<=n;i++){
A.a[i]=a[0][i],A.a[i+n]=a[1][i];
}
for(int i=1;i<=n+n;i++)B.a[i]=A.a[n+n-i+1];
A.getsa(n+n),B.getsa(n+n);
for(int k=(n+1)/2;k>=1;k--){
for(int l=0,r=k;r<=n;l+=k,r+=k){
int x=LCS(0,l,0,r);
int y=LCP(0,l+1,0,r+1);
int z=LCP(0,l+1+y,1,r+y);
if(x+y+z>=k)return k;
}
for(int l=0,r=k;r<=n;l+=k,r+=k){
int x=LCP(0,l+1,1,r);
int y=LCS(0,l,1,r-1);
int z=LCS(0,l-y,0,r-y);
// if(op&&k==3&&l==3){
// fprintf(stderr,"%d %d %d %d %d %s %s %d %d\n",l,r,x,y,z,a[0]+1,a[1]+1,l-y,r-y);
// fprintf(stderr,"%s\n",B.a+1);
// }
if(x+y+z>=k)return k;
}
}
return 0;
}
int main(){
scanf("%d%s%s",&n,a[0]+1,a[1]+1);
int ans=solve(0);
swap(a[0],a[1]);
reverse(a[0]+1,a[0]+1+n);
reverse(a[1]+1,a[1]+1+n);
ans=max(ans,solve(1));
cout<<ans*2<<endl;
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 28292kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 0ms
memory: 28392kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 0ms
memory: 26348kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 28220kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 0ms
memory: 30344kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 30440kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 665ms
memory: 78428kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 663ms
memory: 78324kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 664ms
memory: 78432kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 746ms
memory: 78456kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 345ms
memory: 78248kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 368ms
memory: 78384kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 570ms
memory: 78328kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 0ms
memory: 32300kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 0ms
memory: 34548kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 0ms
memory: 36488kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 0ms
memory: 34496kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 0ms
memory: 30264kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 0ms
memory: 22276kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 0ms
memory: 40644kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 0ms
memory: 40540kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed