QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#725433#9522. A Simple String ProblemqvzeyangAC ✓702ms87428kbC++233.7kb2024-11-08 17:45:102024-11-08 17:45:10

Judging History

你现在查看的是测评时间为 2024-11-08 17:45:10 的历史记录

  • [2024-11-10 22:38:49]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:633ms
  • 内存:87420kb
  • [2024-11-10 22:36:11]
  • hack成功,自动添加数据
  • (/hack/1163)
  • [2024-11-08 17:45:10]
  • 评测
  • 测评结果:100
  • 用时:702ms
  • 内存:87428kb
  • [2024-11-08 17:45:10]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pr pair<int,int>
#define _(x,y) x=(x+y)%mod
#define ll long long
int read(){int d=1,k=0;char c=getchar();
while(!(c>='0' and c<='9' or c=='-'))c=getchar();if(c=='-')d=-1,c=getchar();
while(c>='0' and c<='9')k=(k<<3)+(k<<1)+(c^48),c=getchar();return d*k;}
#define N 800105
#define M 800110
int cnt[M],id[M],rk[M],ork[M],sa[M],height[M],ans,st[M][20],len;
char s[M],S[N],T[N];
inline void suffixArray(){
    int n=len;
    int m=300,p=0;
    for(int i=1;i<=n;++i) cnt[rk[i]=s[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;
    for(int  w=1;p^n;w<<=1,m=p){
        memset(cnt,0,sizeof(cnt)),p=0;
        for(int i=n;i>n-w;--i) id[++p]=i;
        for(int i=1;i<=n;++i) if(sa[i]>w) id[++p]=sa[i]-w;
        for(int i=1;i<=n;++i) cnt[rk[i]]++;
        for(int i=1;i<=m;++i) cnt[i]+=cnt[i-1];
        for(int i=n;i>=1;--i) sa[cnt[rk[id[i]]]--]=id[i];
        memcpy(ork,rk,sizeof(ork)),p=0;
        for(int i=1;i<=n;++i)
            rk[sa[i]]=(ork[sa[i]]==ork[sa[i-1]]&&ork[sa[i]+w]==ork[sa[i-1]+w])?p:++p;
    }
}
inline void getHeight(){
    int n=len;
    for(int i=1,k=0;i<=n;++i){
        if(k) k--;
        while(s[i+k]==s[sa[rk[i]-1]+k]) k++;
        height[rk[i]]=k;
    }
}
int n;
inline int queryMin(int x,int y){
    if(x>y) swap(x,y);
    int k=__lg(y-x+1);
    return min(st[x][k],st[y-(1<<k)+1][k]);
}
inline int querySS(int x,int y){
    x=rk[x],y=rk[y];
    if(x>y) swap(x,y);
    return queryMin(x+1,y);
}
inline int queryTT(int x,int y){
    x=rk[x+2*n+2],y=rk[y+2*n+2];
    if(x>y) swap(x,y);
    return queryMin(x+1,y);
}
inline int queryST(int x,int y){
    x=rk[x],y=rk[y+2*n+2];
    if(x>y) swap(x,y);
    return queryMin(x+1,y);
}
inline int querySSR(int x,int y){
    x=rk[n+1+n-x+1],y=rk[n+1+n-y+1];
    if(x>y) swap(x,y);
    return queryMin(x+1,y);
}
inline int queryTTR(int x,int y){
    x=rk[3*n+3+n-x+1],y=rk[3*n+3+n-y+1];
    if(x>y) swap(x,y);
    return queryMin(x+1,y);
}
inline int querySTR(int x,int y){
    x=rk[n+1+n-x+1],y=rk[3*n+3+n-y+1];
    if(x>y) swap(x,y);
    return queryMin(x+1,y);
}
inline void work(){
    memset(cnt,0,sizeof(cnt));
    memset(id,0,sizeof(id));
    memset(rk,0,sizeof(rk));
    memset(ork,0,sizeof(ork));
    memset(sa,0,sizeof(sa));
    memset(height,0,sizeof(height));
    for(int i=1;i<=n;++i){
        s[i]=S[i];
        s[i+n+1]=S[n-i+1];
        s[i+2*n+2]=T[i];
        s[i+3*n+3]=T[n-i+1];
    }
    s[n+1]='*';
    s[2*n+2]='#';
    s[3*n+3]='@';
    len=4*n+3;
    suffixArray(),getHeight();
    for(int i=1;i<=len;++i) st[i][0]=height[i];
    for(int j=1;j<20;++j){
        for(int i=1;i+(1<<j)-1<=len;++i){
            st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
        }
    }
    for(int l=n;l>=1;--l){
        for(int i=l;i+l<=n;i+=l){
            int j=i+l;
            if(T[i]==T[j]){
                int R=queryTT(i,j)-1;
                int L=queryTTR(i,j)-1;
                int tmp=L+R+querySTR(i-L-1,j-L-1);
                if(tmp>=j-i-1){
                    ans=max(ans,l);
                    return;
                }
            }
            if(S[i]==T[j]){
                int L=querySTR(i,j)-1;
                int R=queryST(i,j)-1;
                int tmp=L+R+queryTT(i+R+1,j+R+1);
                if(tmp>=j-i-1){
                    ans=max(ans,l);
                    return;
                }
            }
        }
    }
}
signed main(){
    n=read();
    scanf("%s%s",S+1,T+2);
	n++;
	S[n]='.';
	T[1]=',';
    work();
    reverse(S+1,S+n+1);
    reverse(T+1,T+n+1);
    swap(S,T);
    work();
    cout<<ans*2;
	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 27976kb

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 4ms
memory: 27840kb

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

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

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

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

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

score: 0
Accepted
time: 4ms
memory: 25976kb

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

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

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 652ms
memory: 87364kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 604ms
memory: 87212kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 617ms
memory: 87404kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 702ms
memory: 87344kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 474ms
memory: 87420kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 502ms
memory: 87428kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 319ms
memory: 87404kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

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

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

score: 0
Accepted
time: 6ms
memory: 27824kb

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

score: 0
Accepted
time: 4ms
memory: 25984kb

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

score: 0
Accepted
time: 4ms
memory: 25980kb

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

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

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

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

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

score: 0
Accepted
time: 4ms
memory: 25916kb

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

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

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed