QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#557318 | #8668. 回文路径 | chrhaa | 0 | 64ms | 5752kb | C++14 | 1.4kb | 2024-09-11 08:57:05 | 2024-09-11 08:57:08 |
Judging History
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);
if(j) 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);
if(j) 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;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 30
Accepted
time: 1ms
memory: 3832kb
input:
1000 mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...
output:
6
result:
ok single line: '6'
Test #2:
score: 30
Accepted
time: 0ms
memory: 4308kb
input:
1000 wvitzoxwlmhexjuqvoxksetoupgkhattucdzfevqorkdlsymjuvhobdrjsodtipwpfhipsdnyvqtsbbasrrvyybijzmpwseckztnpnkqswgkaeivflhwevhxcchjsnelqcixexkntwiuolsditpdwypgerzijziyrgqkwuucnqaehuwkpyrmwewjitvsaebyytznbtnkulnepceeloyjpfhcdpqfqhvzsmkcynjwztmkbnqaxnikfuiutocahdfbvsgdskgwqmzizzjlbqxnngftdohetabpjzpqzyc...
output:
7
result:
ok single line: '7'
Test #3:
score: 30
Accepted
time: 1ms
memory: 4228kb
input:
1000 abababaabaababbbbabbbbabbbbbbabbbaabbbaababaabaabbabbbbaabbaabaaaabbaaabbbbaaaaaabbbbababaababbaabbbbbbbbabbaababbbbabbaabbbabaaababbaababbbaabaabaababaaababbaaaababbbbbaaabbaabbaaabbaaaaabaaaaaabbbbbaaabbbbbaabbbbababaabaabbbbaaaaababaaaababbbbbbaababbbaaaababaabaabaabaaaaaabbabbabbbbbbbbbbabb...
output:
28
result:
ok single line: '28'
Test #4:
score: 30
Accepted
time: 1ms
memory: 4204kb
input:
1000 ababbababababbaababaaabaabaababbaabbbabaababbaaababbabbbbaabbababbbababbabababbaabbbaababbabaaaaabbbbbaaaaaaaaabbbbaabbbaabbababaaabababbaaaabababbbaabaabbabbaabaaaaaaabaaabaaababaaaababbaaabaabbbbbbaabbabaaabaabbbbabbababbbaaaaabbabbaabbaabbaabaaabaaabbbbbaabaaaaaababbbbbabbbabbbabababbbbbabaa...
output:
27
result:
ok single line: '27'
Test #5:
score: 30
Accepted
time: 1ms
memory: 3624kb
input:
1000 abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabba...
output:
987
result:
ok single line: '987'
Test #6:
score: 30
Accepted
time: 1ms
memory: 2468kb
input:
1000 aaaaaaababbabbabaabaaaaababaaaaaabaabaaaabaaaaaaabbbabaabbaaabaaaaaaabaaaaaaaabaaabbaababaaaaaaaaabbaabbabbaaaaabaaaaaaaabbaaabaaaaaaaaaaabaabbbbbaaaabaaaaaaaaabbbaaaaabaaabaaaaaaaaaaaaaababaaaaabbaabbaaaabaabaaaababaaaaaababaaaaabaaaaaaabaaaababaaaabbaaaabaaaaabaaaaaaaabaaaaaaabaaaaaaaaaaaabaa...
output:
45
result:
ok single line: '45'
Test #7:
score: 30
Accepted
time: 1ms
memory: 3716kb
input:
1000 aaaaaabaaaaaaaababaaaaaaababaaaabaabaaaaabaabaaaabbaaaaabaababaaaaaaaaaaabaaaabaaaaaaaaaaaaaaaaaabbaaaaaaababaabaaaabababaaaaabbaaaaaabbababaaabbaaababbaaaabbababaaaaaaaaabbbaaaababaaaaabaaaabbaabaaaaaabbaabaaaaaaaaaaabaaaababbaaaaaaaababbabaaaaaaaaabaaaabaaaaabaaaaaaaaaaaabaaaabaaababaabaabaab...
output:
45
result:
ok single line: '45'
Test #8:
score: 0
Wrong Answer
time: 1ms
memory: 4116kb
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: 64ms
memory: 5728kb
input:
100000 ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...
output:
9
result:
ok single line: '9'
Test #12:
score: 0
Wrong Answer
time: 64ms
memory: 5752kb
input:
100000 fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...
output:
10
result:
wrong answer 1st lines differ - expected: '9', found: '10'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%