QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#557312#8668. 回文路径chrhaa0 83ms5728kbC++141.3kb2024-09-11 08:54:582024-09-11 08:54:58

Judging History

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

  • [2024-09-11 08:54:58]
  • 评测
  • 测评结果:0
  • 用时:83ms
  • 内存:5728kb
  • [2024-09-11 08:54:58]
  • 提交

answer

#include<stdio.h>
#include<algorithm>
const int N=100005;

#define ull long long
const ull B=233,P=1226999999;

int n,ans;
ull h1[2][N],h2[2][N],pw[N];
char s[2][N];

inline ull H1(int f,int l,int r){
    return (h1[f][r]+P-h1[f][l-1]*pw[r-l+1]%P)%P;
}

inline ull H2(int f,int l,int r){
    return (h2[f][l]+P-h2[f][r+1]*pw[r-l+1]%P)%P;
}

int calc(int x,int y,int fx,int fy){
    int l=0,r=std::min(x,n-y+1),z;

    while(l<r){
        z=l+r+1>>1;

        if(H2(fx,x-z+1,x)==H1(fy,y,y+z-1)) l=z;
        else r=z-1;
    }

    return l;
}

signed main(){
    int i,j;
    scanf("%d%s%s",&n,s[0]+1,s[1]+1);

    for(i=pw[0]=1;i<N;i++) pw[i]=pw[i-1]*B%P;
    for(i=0;i<2;i++){
        for(j=1;j<=n;j++) h1[i][j]=(h1[i][j-1]*B+s[i][j])%P;
        for(j=n;j>=1;j--) h2[i][j]=(h2[i][j+1]*B+s[i][j])%P;
    }

    for(i=1;i<=n;i++){
        j=calc(i,i,0,0);
        ans=std::max(ans,(j+calc(i-j,i+j-1,0,1))*2-1);
    }for(i=1;i<n;i++){
        j=calc(i,i+1,0,0);
        ans=std::max(ans,(j+calc(i-j,i+j,0,1))*2);
    }for(i=1;i<=n;i++){
        j=calc(i,i,1,1);
        ans=std::max(ans,(j+calc(i-j+1,i+j,0,1))*2-1);
    }for(i=1;i<n;i++){
        j=calc(i,i+1,1,1);
        ans=std::max(ans,(j+calc(i-j,i+j,0,1))*2);
    }for(i=1;i<=n;i++) ans=std::max(ans,calc(i,i,0,1)*2);

    printf("%d\n",ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

input:

1000
mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...

output:

6

result:

ok single line: '6'

Test #2:

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

input:

1000
wvitzoxwlmhexjuqvoxksetoupgkhattucdzfevqorkdlsymjuvhobdrjsodtipwpfhipsdnyvqtsbbasrrvyybijzmpwseckztnpnkqswgkaeivflhwevhxcchjsnelqcixexkntwiuolsditpdwypgerzijziyrgqkwuucnqaehuwkpyrmwewjitvsaebyytznbtnkulnepceeloyjpfhcdpqfqhvzsmkcynjwztmkbnqaxnikfuiutocahdfbvsgdskgwqmzizzjlbqxnngftdohetabpjzpqzyc...

output:

7

result:

ok single line: '7'

Test #3:

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

input:

1000
abababaabaababbbbabbbbabbbbbbabbbaabbbaababaabaabbabbbbaabbaabaaaabbaaabbbbaaaaaabbbbababaababbaabbbbbbbbabbaababbbbabbaabbbabaaababbaababbbaabaabaababaaababbaaaababbbbbaaabbaabbaaabbaaaaabaaaaaabbbbbaaabbbbbaabbbbababaabaabbbbaaaaababaaaababbbbbbaababbbaaaababaabaabaabaaaaaabbabbabbbbbbbbbbabb...

output:

28

result:

ok single line: '28'

Test #4:

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

input:

1000
ababbababababbaababaaabaabaababbaabbbabaababbaaababbabbbbaabbababbbababbabababbaabbbaababbabaaaaabbbbbaaaaaaaaabbbbaabbbaabbababaaabababbaaaabababbbaabaabbabbaabaaaaaaabaaabaaababaaaababbaaabaabbbbbbaabbabaaabaabbbbabbababbbaaaaabbabbaabbaabbaabaaabaaabbbbbaabaaaaaababbbbbabbbabbbabababbbbbabaa...

output:

27

result:

ok single line: '27'

Test #5:

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

input:

1000
abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabba...

output:

987

result:

ok single line: '987'

Test #6:

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

input:

1000
aaaaaaababbabbabaabaaaaababaaaaaabaabaaaabaaaaaaabbbabaabbaaabaaaaaaabaaaaaaaabaaabbaababaaaaaaaaabbaabbabbaaaaabaaaaaaaabbaaabaaaaaaaaaaabaabbbbbaaaabaaaaaaaaabbbaaaaabaaabaaaaaaaaaaaaaababaaaaabbaabbaaaabaabaaaababaaaaaababaaaaabaaaaaaabaaaababaaaabbaaaabaaaaabaaaaaaaabaaaaaaabaaaaaaaaaaaabaa...

output:

45

result:

ok single line: '45'

Test #7:

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

input:

1000
aaaaaabaaaaaaaababaaaaaaababaaaabaabaaaaabaabaaaabbaaaaabaababaaaaaaaaaaabaaaabaaaaaaaaaaaaaaaaaabbaaaaaaababaabaaaabababaaaaabbaaaaaabbababaaabbaaababbaaaabbababaaaaaaaaabbbaaaababaaaaabaaaabbaabaaaaaabbaabaaaaaaaaaaabaaaababbaaaaaaaababbabaaaaaaaaabaaaabaaaaabaaaaaaaaaaaabaaaabaaababaabaabaab...

output:

45

result:

ok single line: '45'

Test #8:

score: 0
Wrong Answer
time: 1ms
memory: 4044kb

input:

1000
aabaaaabaaaabaaabaabbbaabaabbbaaaaaaaaaabaaaaabaababaabaabaaaaaaaaaabbabbaaaaaaaabaabbbbbaaaabbabbbaaaaaabababbaaaabaaaaaaaaabaaaaaaaabaaaaaabbaaaaabaaaaaababaaababaaaabaaaaaabaaaaaaabaaaaabbaaaaabaababaaaabbaaabbaabaabaaaaababbababaaabbbabaabaaabaaabaababbabaababaaaaabaaababaaaaaaaaaabbaaaabaa...

output:

40

result:

wrong answer 1st lines differ - expected: '36', found: '40'

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 20
Accepted
time: 83ms
memory: 5724kb

input:

100000
ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...

output:

9

result:

ok single line: '9'

Test #12:

score: 0
Wrong Answer
time: 78ms
memory: 5728kb

input:

100000
fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...

output:

10

result:

wrong answer 1st lines differ - expected: '9', found: '10'

Subtask #3:

score: 0
Skipped

Dependency #1:

0%