QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#557233#8668. 回文路径AllenJYL100 ✓77ms7996kbC++144.5kb2024-09-11 08:20:172024-09-11 08:20:17

Judging History

你现在查看的是最新测评结果

  • [2024-09-11 08:20:17]
  • 评测
  • 测评结果:100
  • 用时:77ms
  • 内存:7996kb
  • [2024-09-11 08:20:17]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define int long long
// #define ls p<<1
// #define rs p<<1|1
#define msp(_array) memset(_array,0x3f,sizeof _array)
#define ms0(_array) memset(_array,0,sizeof _array)
#define msn(_array) memset(_array,-1,sizeof _array)
#define mc(_tar,_array) memcpy(_tar,_array,sizeof _tar)
#define pii pair<int,int>
#define endl '\n'

bool bg_memory;
const int mod=1226999999;
const int inf=2147483647;
const int bs=23333;
const double eps=1e-6;
const int N=1e5+7,M=1e5+7;
inline void cmax(int &a,int b){a=a<b?b:a;}
inline void cmin(int &a,int b){a=a>b?b:a;}
inline int qp(int a,int b){int res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}

int n;
string s,t;
int hs[N],ht[N],rhs[N],rht[N];
int pw[N];
int ans;

mt19937 rnd(time(0));
int Case=1;
void Main(){
    
    cin>>n>>s>>t;
    s=' '+s;
    t=' '+t;
    pw[0]=1;
    for(int i=1;i<=n;i++) pw[i]=pw[i-1]*bs%mod;
    for(int i=1;i<=n;i++) hs[i]=(hs[i-1]*bs%mod+s[i])%mod;
    for(int i=1;i<=n;i++) ht[i]=(ht[i-1]*bs%mod+t[i])%mod;
    for(int i=n;i>=1;i--) rhs[i]=(rhs[i+1]*bs%mod+s[i])%mod;
    for(int i=n;i>=1;i--) rht[i]=(rht[i+1]*bs%mod+t[i])%mod;
    for(int i=1;i<=n;i++){
        int l=1,r=min(i,n-i+1),res=1;
        while(l<=r){
            int mid=l+r>>1;
            if((hs[i]-hs[i-mid]*pw[mid]%mod+mod)%mod==(rhs[i]-rhs[i+mid]*pw[mid]%mod+mod)%mod) res=mid,l=mid+1;
            else r=mid-1;
        }
        l=0,r=min(i-res,n-(i+res-1)+1);
        int res2=0;
        while(l<=r){
            int mid=l+r>>1;
            if((hs[i-res]-hs[i-res-mid]*pw[mid]%mod+mod)%mod==(rht[i+res-1]-rht[i+res-1+mid]*pw[mid]%mod+mod)%mod) res2=mid,l=mid+1;
            else r=mid-1;
        }
        cmax(ans,2*res-1+2*res2);
    }
    for(int i=1;i<n;i++){
        int l=0,r=min(i,n-i),res=0;
        while(l<=r){
            int mid=l+r>>1;
            if((hs[i]-hs[i-mid]*pw[mid]%mod+mod)%mod==(rhs[i+1]-rhs[i+mid+1]*pw[mid]%mod+mod)%mod) res=mid,l=mid+1;
            else r=mid-1;
        }
        l=0,r=min(i-res,n-(i+res)+1);
        int res2=0;
        while(l<=r){
            int mid=l+r>>1;
            if((hs[i-res]-hs[i-res-mid]*pw[mid]%mod+mod)%mod==(rht[i+res]-rht[i+res+mid]*pw[mid]%mod+mod)%mod) res2=mid,l=mid+1;
            else r=mid-1;
        }
        cmax(ans,2*res+2*res2);
    }
    for(int i=1;i<=n;i++){
        int l=1,r=min(i,n-i+1),res=1;
        while(l<=r){
            int mid=l+r>>1;
            if((ht[i]-ht[i-mid]*pw[mid]%mod+mod)%mod==(rht[i]-rht[i+mid]*pw[mid]%mod+mod)%mod) res=mid,l=mid+1;
            else r=mid-1;
        }
        l=0,r=min(i-res+1,n-(i+res-1));
        int res2=0;
        while(l<=r){
            int mid=l+r>>1;
            if((hs[i-res+1]-hs[i-res+1-mid]*pw[mid]%mod+mod)%mod==(rht[i+res]-rht[i+res+mid]*pw[mid]%mod+mod)%mod) res2=mid,l=mid+1;
            else r=mid-1;
        }
        cmax(ans,2*res-1+2*res2);
    }
    for(int i=1;i<n;i++){
        int l=0,r=min(i,n-i),res=0;
        while(l<=r){
            int mid=l+r>>1;
            if((ht[i]-ht[i-mid]*pw[mid]%mod+mod)%mod==(rht[i+1]-rht[i+1+mid]*pw[mid]%mod+mod)%mod) res=mid,l=mid+1;
            else r=mid-1;
        }
        l=0,r=min(i-res+1,n-(i+res));
        int res2=0;
        while(l<=r){
            int mid=l+r>>1;
            if((hs[i-res+1]-hs[i-res+1-mid]*pw[mid]%mod+mod)%mod==(rht[i+res+1]-rht[i+res+mid+1]*pw[mid]%mod+mod)%mod) res2=mid,l=mid+1;
            else r=mid-1;
        }
        cmax(ans,2*res+2*res2);
    }
    for(int i=1;i<=n;i++){
        int l=1,r=min(i,n-i+1),res=0;
        while(l<=r){
            int mid=l+r>>1;
            if((hs[i]-hs[i-mid]*pw[mid]%mod+mod)%mod==(rht[i]-rht[i+mid]*pw[mid]%mod+mod)%mod) res=mid,l=mid+1;
            else r=mid-1;
        }
        cmax(ans,2*res);
    }
    cout<<ans<<endl;

    return;
}
string RdFile="c";
bool en_memory;

signed main(){
    auto bg_clock=chrono::high_resolution_clock::now();
#ifdef ONLINE_JUDGE
    // freopen((RdFile+".in").c_str(),"r",stdin);
    // freopen((RdFile+".out").c_str(),"w",stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // cin>>Case;
    while(Case--) Main();
    auto en_clock=chrono::high_resolution_clock::now();
    auto duration_clock=chrono::duration_cast<chrono::microseconds>(en_clock-bg_clock);
#ifndef ONLINE_JUDGE
    cerr<<endl<<"code_time_used: "<<duration_clock.count()*0.001<<"ms"<<endl;
    cerr<<"code_memory_used: "<<(&en_memory-&bg_memory)/1024.0/1024<<"MB"<<endl;
#endif
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 30
Accepted

Test #1:

score: 30
Accepted
time: 0ms
memory: 3760kb

input:

1000
mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...

output:

6

result:

ok single line: '6'

Test #2:

score: 30
Accepted
time: 1ms
memory: 3772kb

input:

1000
wvitzoxwlmhexjuqvoxksetoupgkhattucdzfevqorkdlsymjuvhobdrjsodtipwpfhipsdnyvqtsbbasrrvyybijzmpwseckztnpnkqswgkaeivflhwevhxcchjsnelqcixexkntwiuolsditpdwypgerzijziyrgqkwuucnqaehuwkpyrmwewjitvsaebyytznbtnkulnepceeloyjpfhcdpqfqhvzsmkcynjwztmkbnqaxnikfuiutocahdfbvsgdskgwqmzizzjlbqxnngftdohetabpjzpqzyc...

output:

7

result:

ok single line: '7'

Test #3:

score: 30
Accepted
time: 1ms
memory: 3888kb

input:

1000
abababaabaababbbbabbbbabbbbbbabbbaabbbaababaabaabbabbbbaabbaabaaaabbaaabbbbaaaaaabbbbababaababbaabbbbbbbbabbaababbbbabbaabbbabaaababbaababbbaabaabaababaaababbaaaababbbbbaaabbaabbaaabbaaaaabaaaaaabbbbbaaabbbbbaabbbbababaabaabbbbaaaaababaaaababbbbbbaababbbaaaababaabaabaabaaaaaabbabbabbbbbbbbbbabb...

output:

28

result:

ok single line: '28'

Test #4:

score: 30
Accepted
time: 1ms
memory: 3988kb

input:

1000
ababbababababbaababaaabaabaababbaabbbabaababbaaababbabbbbaabbababbbababbabababbaabbbaababbabaaaaabbbbbaaaaaaaaabbbbaabbbaabbababaaabababbaaaabababbbaabaabbabbaabaaaaaaabaaabaaababaaaababbaaabaabbbbbbaabbabaaabaabbbbabbababbbaaaaabbabbaabbaabbaabaaabaaabbbbbaabaaaaaababbbbbabbbabbbabababbbbbabaa...

output:

27

result:

ok single line: '27'

Test #5:

score: 30
Accepted
time: 1ms
memory: 3820kb

input:

1000
abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabba...

output:

987

result:

ok single line: '987'

Test #6:

score: 30
Accepted
time: 1ms
memory: 3792kb

input:

1000
aaaaaaababbabbabaabaaaaababaaaaaabaabaaaabaaaaaaabbbabaabbaaabaaaaaaabaaaaaaaabaaabbaababaaaaaaaaabbaabbabbaaaaabaaaaaaaabbaaabaaaaaaaaaaabaabbbbbaaaabaaaaaaaaabbbaaaaabaaabaaaaaaaaaaaaaababaaaaabbaabbaaaabaabaaaababaaaaaababaaaaabaaaaaaabaaaababaaaabbaaaabaaaaabaaaaaaaabaaaaaaabaaaaaaaaaaaabaa...

output:

45

result:

ok single line: '45'

Test #7:

score: 30
Accepted
time: 1ms
memory: 3824kb

input:

1000
aaaaaabaaaaaaaababaaaaaaababaaaabaabaaaaabaabaaaabbaaaaabaababaaaaaaaaaaabaaaabaaaaaaaaaaaaaaaaaabbaaaaaaababaabaaaabababaaaaabbaaaaaabbababaaabbaaababbaaaabbababaaaaaaaaabbbaaaababaaaaabaaaabbaabaaaaaabbaabaaaaaaaaaaabaaaababbaaaaaaaababbabaaaaaaaaabaaaabaaaaabaaaaaaaaaaaabaaaabaaababaabaabaab...

output:

45

result:

ok single line: '45'

Test #8:

score: 30
Accepted
time: 1ms
memory: 3984kb

input:

1000
aabaaaabaaaabaaabaabbbaabaabbbaaaaaaaaaabaaaaabaababaabaabaaaaaaaaaabbabbaaaaaaaabaabbbbbaaaabbabbbaaaaaabababbaaaabaaaaaaaaabaaaaaaaabaaaaaabbaaaaabaaaaaababaaababaaaabaaaaaabaaaaaaabaaaaabbaaaaabaababaaaabbaaabbaabaabaaaaababbababaaabbbabaabaaabaaabaababbabaababaaaaabaaababaaaaaaaaaabbaaaabaa...

output:

36

result:

ok single line: '36'

Test #9:

score: 30
Accepted
time: 1ms
memory: 3984kb

input:

1000
aaaaaabaabaaaaaaabaaaaaabaabaaaaaaaaabaabaaaaaaababaaaaabaaabaabaaabaaaaaaaaaaaaabbbbbabaaaaaaabaaaaabaaabaaaaabababaaabaaabaabaabaaaabbaabaaaaaaaaaaaaaaabbaaaaabaabbabbbaaabbbabaababbaabaaaabbaaaabaabbbaaaaaaaaaabaabaaaabbaaaabbbbaaabaaaaabaaababaaaaaaaaaabbabbabaaaaaaaaaaaaaaaabaababbaaaababa...

output:

50

result:

ok single line: '50'

Test #10:

score: 30
Accepted
time: 1ms
memory: 3652kb

input:

1000
aaccbdbabdaaddabaabaaaacbbccdbabbaacabcdababdcacadababaadaaaadabacababcdbaabaaaabdbabbdcaacccaaacababaacbcacaaabbabbaaabcbaaabaababbaaacbaacaaacabdccbbbaabaccacadbbcaabacadaababbaaabababbacaabbaaabcdaabaaaaaabaababaabcabacaabacaaaaaacaaabcbcabcbbcbbbaacaadadbadbbadcabababcabbcbbdadbdababaaadcab...

output:

20

result:

ok single line: '20'

Subtask #2:

score: 20
Accepted

Test #11:

score: 20
Accepted
time: 63ms
memory: 7868kb

input:

100000
ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...

output:

9

result:

ok single line: '9'

Test #12:

score: 20
Accepted
time: 67ms
memory: 7708kb

input:

100000
fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...

output:

9

result:

ok single line: '9'

Test #13:

score: 20
Accepted
time: 68ms
memory: 7780kb

input:

99999
biwnbsgdlxognjnepijlgbfbbahicjfqhdhcielcovdflacbrgcfapifaylqfmvipcccoofthuutfheboncacenchdgfljpidjbasdsikduidkbdqckmlnbfaidlincqkccbbpmnqnpbjoclgeduitraqmdfgdqinhddgberlbnlgggoafgqllbifekoccpgemcgdiiackkcfjgddhieabhzdjfwegcbuncdadebglitgwcbpmclfijmqtbbnbbrcehhanjgbddiaoimmkehtloreemecckjejifck...

output:

11

result:

ok single line: '11'

Test #14:

score: 20
Accepted
time: 62ms
memory: 7732kb

input:

99999
chgjcjipccsmclcpjqmbrcpaqdggbdodxbcejbklpjhkefeidkjojjjbljhtykbcdgnnjeictgjgliegyfilmlkqkgddpefibjusamblbpqfbbvcfkgfagikbujlbjvenjbmcadceadnltdeksatckmkjkscojeqbpaaglggxhideqhkhibchdasadfggcoihhcwlphbeevohhohtthepedqfggbdglidnatocrkhnkijraddqbesaiajimdhdmvbgodlcglqqmkeehcfabeaatjdinzhijewfoxhh...

output:

9

result:

ok single line: '9'

Test #15:

score: 20
Accepted
time: 55ms
memory: 7676kb

input:

99999
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

99999

result:

ok single line: '99999'

Subtask #3:

score: 50
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #16:

score: 50
Accepted
time: 68ms
memory: 7732kb

input:

100000
vucutyzmjlnyadjbpqkrlqvzuponzxrvqsqqgbemhzjftdkksfgspeuonmjwlbirvszhcafcxpeubixvxetwyyqmftbobhodwaiwrcwdvddohalyqgaatvpflorvjypszbvzpwiaxxgievaozquixcndkxqfxcxaiygyqcgdebogwzquvqfljgjcvvhpirfzqlkwctibngdsffpormliyhrkcbxwxoaoovaawldfenziwnlahllzhjsvdhzekcqekayusmvzrgsdiiymjxfiddhawhgxathvnsedf...

output:

10

result:

ok single line: '10'

Test #17:

score: 50
Accepted
time: 67ms
memory: 7740kb

input:

100000
fotxrzsqxuaaiiqmiymhtfdipylgdmxizgzqrgbrmdemonbisusgbmmsgtyoaqgdmxwoxayxkszpvpypzjoapilopvhyiyhckcccaalqriunudgfifgvdiufjtukpsmdfjjzftszwizrwoxuqsujchtrywpiiineoscbvarbalizfyydbctxpuwndzgshavpygfcmxkorbcppbatauqqkumaqsjcupnihewaukjajqgdvatobxjgdcbevlxpkjdvpofwtctivkexpwnbwvwbhcmlivuvifpptiupy...

output:

9

result:

ok single line: '9'

Test #18:

score: 50
Accepted
time: 70ms
memory: 7992kb

input:

100000
baaabababbbaabbbbaabbabbababbbbbaaaaabaabbbbbbaaabaabaaabababbabbabbaababbaababbbabaaaaabbbabbabaaaabaabbbbababaaaaabbbbbabbbababbbbbaaabbaaabaabaaababbababbabaaaaaaaababaaabaababbbababbbbabbbabaaababbababbbababaabbaabbabaaaabaaabbbabbaabbabbbbbbabbbbaaaaaaaaaaabbbaabaaaabbbabbbaabababbbbaabb...

output:

40

result:

ok single line: '40'

Test #19:

score: 50
Accepted
time: 76ms
memory: 7684kb

input:

100000
babbbbaabaaaaaaaaaabbbbababababababababbabaaabbaaaaabaaaabaaaaababaabaabaabbbbabbbaabababbbaaabaaaaaaababaabababababbaabbbaabaabbbbbbbabaabbaabaaaababbbaabaaabaaaabbabbababbaabbabbbaabbbaababbaabaabaabbabbbabaaaaaaaaaabaabbabaaaaababaabbababbbabababbbbabbbbababababaabbabbababbaababababbbbaaba...

output:

43

result:

ok single line: '43'

Test #20:

score: 50
Accepted
time: 76ms
memory: 7964kb

input:

100000
aabaabbaaaaabbbbbaaaaaaaaaaaaaabbaaaaaaaaabaaaabbaaaaaabaaaaabaabbaaabababaaabbaaaaaaaaaabbabbbaaaaaaabaaabbbaabaaabaaabaaaaaaaaaabaabaaaababaaaaaabbaaaaaaababaabaaaaabababaaaaaaaaaababaaaababbaaabaaaabaaaaabaababbaaaaabbaaabaabaabaaaaababaaaaabbaaaabaaaaaaabaaaaaaaaabaabaaaaaabaababbbabaaaba...

output:

75

result:

ok single line: '75'

Test #21:

score: 50
Accepted
time: 77ms
memory: 7900kb

input:

100000
aaaabaabaaabaabbaaaabbbaaaaaaabaabaabaabaaaababaaaaabaaaaabbabaabbaabaaaaaabaaaaaaaaaaaaabaabbabaaaaaabaaaaaaaaaaaabaaaabbbabaaaaaabaaaababaaaabaaaaaabbaaaaaaaaabababaaaaabaabababaaabbababaaaaababababbaaaaaabaabaaaabbababbbaaabaaaabaabaaaaabaabaaaaaabbbaaaaaaabababababbaaabaaabaaababaaaabaaaa...

output:

58

result:

ok single line: '58'

Test #22:

score: 50
Accepted
time: 75ms
memory: 7996kb

input:

100000
abbaaaaaaabaaaaaaaabaaaaaaaaaaaaaaaaabbabaaabaaaaaaaaaaaaaaabaaabbbaabaaaaabaaaaaaabaaaaabaabaabaaaababaaaaaaaaaaaaaaaaabaaabbabaaaaaaabaaaaaaabaaaaaabaaaaabaaabbaaaabbaabbaaababaababaaaaaabaaaaabaaaaaaaaaaaaababaaaaabaaaaaabbbabaaaaaaaaaaaaabaaaaaaaabbbaabaaabaaabaaabbabaabaaabbabaaaaaaaabba...

output:

67

result:

ok single line: '67'

Test #23:

score: 50
Accepted
time: 75ms
memory: 7676kb

input:

100000
bbaaaaabaaaaaaaaaabbaabaaaaaaabbbaabababaaababbaaaabaaaaaaaaaabaaaabbaaaaabaaaaaabbaabbbbaaabbaaaaaabbabaaabaababbaababaaabaaaaaaaaaabaaaaabbaaaaabbaaaabaaabababbbaabaaaaabaabaaaaaaabaaaaaaabaabababbbaaaaaaaaaaaaaaaaabaaaaaaabaaaaaababbbababaabaaabbbaaaaabaaaaaaabaabababaaaaaabaaaabbaabababaa...

output:

55

result:

ok single line: '55'

Test #24:

score: 50
Accepted
time: 67ms
memory: 7672kb

input:

100000
cabcacbbacbbaacbaabbaabbaabacdcadbbccabbccbbaabacacbabaccbaabbbaaabaddbcaccdcaababaaabbbbbcdacaabababcbbcbcabbbdbbbcadaadabcabbacabbdbbcaaabacaabbabbabacbabbabaadabbabdbabcbdcaacaddbbbabdabaaabcabcababbcbbaaccabbbbacaabbacdaaaabaaaaccaaabaaccbaccbbababdacaacabcaaabbaaacbcbaaabcaaabcaabbabbcad...

output:

25

result:

ok single line: '25'

Test #25:

score: 50
Accepted
time: 68ms
memory: 7796kb

input:

100000
abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbab...

output:

96421

result:

ok single line: '96421'

Test #26:

score: 50
Accepted
time: 0ms
memory: 3752kb

input:

5
pkusc
pkukp

output:

6

result:

ok single line: '6'