QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#557324 | #8668. 回文路径 | chrhaa | 0 | 82ms | 5696kb | C++14 | 1.3kb | 2024-09-11 08:58:39 | 2024-09-11 08:58:39 |
Judging History
answer
#include<stdio.h>
#include<algorithm>
const int N=100005;
#define ull long long
const ull B=1441,P=998244353;
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: 2448kb
input:
1000 mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...
output:
6
result:
ok single line: '6'
Test #2:
score: 30
Accepted
time: 1ms
memory: 3960kb
input:
1000 wvitzoxwlmhexjuqvoxksetoupgkhattucdzfevqorkdlsymjuvhobdrjsodtipwpfhipsdnyvqtsbbasrrvyybijzmpwseckztnpnkqswgkaeivflhwevhxcchjsnelqcixexkntwiuolsditpdwypgerzijziyrgqkwuucnqaehuwkpyrmwewjitvsaebyytznbtnkulnepceeloyjpfhcdpqfqhvzsmkcynjwztmkbnqaxnikfuiutocahdfbvsgdskgwqmzizzjlbqxnngftdohetabpjzpqzyc...
output:
7
result:
ok single line: '7'
Test #3:
score: 30
Accepted
time: 1ms
memory: 2484kb
input:
1000 abababaabaababbbbabbbbabbbbbbabbbaabbbaababaabaabbabbbbaabbaabaaaabbaaabbbbaaaaaabbbbababaababbaabbbbbbbbabbaababbbbabbaabbbabaaababbaababbbaabaabaababaaababbaaaababbbbbaaabbaabbaaabbaaaaabaaaaaabbbbbaaabbbbbaabbbbababaabaabbbbaaaaababaaaababbbbbbaababbbaaaababaabaabaabaaaaaabbabbabbbbbbbbbbabb...
output:
28
result:
ok single line: '28'
Test #4:
score: 30
Accepted
time: 0ms
memory: 3992kb
input:
1000 ababbababababbaababaaabaabaababbaabbbabaababbaaababbabbbbaabbababbbababbabababbaabbbaababbabaaaaabbbbbaaaaaaaaabbbbaabbbaabbababaaabababbaaaabababbbaabaabbabbaabaaaaaaabaaabaaababaaaababbaaabaabbbbbbaabbabaaabaabbbbabbababbbaaaaabbabbaabbaabbaabaaabaaabbbbbaabaaaaaababbbbbabbbabbbabababbbbbabaa...
output:
27
result:
ok single line: '27'
Test #5:
score: 30
Accepted
time: 1ms
memory: 4020kb
input:
1000 abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabba...
output:
987
result:
ok single line: '987'
Test #6:
score: 30
Accepted
time: 0ms
memory: 3816kb
input:
1000 aaaaaaababbabbabaabaaaaababaaaaaabaabaaaabaaaaaaabbbabaabbaaabaaaaaaabaaaaaaaabaaabbaababaaaaaaaaabbaabbabbaaaaabaaaaaaaabbaaabaaaaaaaaaaabaabbbbbaaaabaaaaaaaaabbbaaaaabaaabaaaaaaaaaaaaaababaaaaabbaabbaaaabaabaaaababaaaaaababaaaaabaaaaaaabaaaababaaaabbaaaabaaaaabaaaaaaaabaaaaaaabaaaaaaaaaaaabaa...
output:
45
result:
ok single line: '45'
Test #7:
score: 30
Accepted
time: 1ms
memory: 4376kb
input:
1000 aaaaaabaaaaaaaababaaaaaaababaaaabaabaaaaabaabaaaabbaaaaabaababaaaaaaaaaaabaaaabaaaaaaaaaaaaaaaaaabbaaaaaaababaabaaaabababaaaaabbaaaaaabbababaaabbaaababbaaaabbababaaaaaaaaabbbaaaababaaaaabaaaabbaabaaaaaabbaabaaaaaaaaaaabaaaababbaaaaaaaababbabaaaaaaaaabaaaabaaaaabaaaaaaaaaaaabaaaabaaababaabaabaab...
output:
45
result:
ok single line: '45'
Test #8:
score: 0
Wrong Answer
time: 1ms
memory: 2376kb
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: 82ms
memory: 5632kb
input:
100000 ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...
output:
9
result:
ok single line: '9'
Test #12:
score: 0
Wrong Answer
time: 81ms
memory: 5696kb
input:
100000 fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...
output:
10
result:
wrong answer 1st lines differ - expected: '9', found: '10'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%