QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#708940#9522. A Simple String Problemqzez#AC ✓729ms78432kbC++142.8kb2024-11-04 09:54:222024-11-04 09:54:22

Judging History

你现在查看的是测评时间为 2024-11-04 09:54:22 的历史记录

  • [2024-11-10 22:38:12]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:760ms
  • 内存:78460kb
  • [2024-11-10 22:36:11]
  • hack成功,自动添加数据
  • (/hack/1163)
  • [2024-11-06 21:49:49]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:746ms
  • 内存:78456kb
  • [2024-11-06 21:48:00]
  • hack成功,自动添加数据
  • (/hack/1142)
  • [2024-11-04 09:54:22]
  • 评测
  • 测评结果:100
  • 用时:729ms
  • 内存:78432kb
  • [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,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 30340kb

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 0ms
memory: 28336kb

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

score: 0
Accepted
time: 0ms
memory: 26284kb

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 0ms
memory: 28388kb

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

score: 0
Accepted
time: 0ms
memory: 28256kb

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

score: 0
Accepted
time: 0ms
memory: 30300kb

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 656ms
memory: 78248kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 645ms
memory: 78424kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 649ms
memory: 78432kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 729ms
memory: 78324kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 343ms
memory: 78288kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 377ms
memory: 78324kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 518ms
memory: 78324kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

score: 0
Accepted
time: 0ms
memory: 34392kb

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

score: 0
Accepted
time: 2ms
memory: 36584kb

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

score: 0
Accepted
time: 0ms
memory: 36592kb

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

score: 0
Accepted
time: 0ms
memory: 30296kb

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

score: 0
Accepted
time: 3ms
memory: 28276kb

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

score: 0
Accepted
time: 0ms
memory: 22244kb

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

score: 0
Accepted
time: 0ms
memory: 40580kb

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

score: 0
Accepted
time: 0ms
memory: 36484kb

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed