QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#557578 | #8668. 回文路径 | h_rains | 100 ✓ | 26ms | 7840kb | C++14 | 3.5kb | 2024-09-11 10:21:17 | 2024-09-11 10:21:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int maxn=1e5+5;
const int base=233;
int pw[maxn];
int h1[maxn],h2[maxn],h3[maxn],h4[maxn];
int solve1(int l,int r)
{
return h1[r]-h1[l-1]*pw[r-l+1];
}
int solve2(int l,int r)
{
return h2[l]-h2[r+1]*pw[r-l+1];
}
int solve3(int l,int r)
{
return h3[r]-h3[l-1]*pw[r-l+1];
}
int solve4(int l,int r)
{
return h4[l]-h4[r+1]*pw[r-l+1];
}
signed main()
{
int n,ans=0;
cin>>n;
string s,s2;
cin>>s>>s2;pw[0]=1;
for(int i=1;i<=n;i++) pw[i]=pw[i-1]*base;
for(int i=1;i<=n;i++) h1[i]=h1[i-1]*base+(s[i-1]-'a');
for(int i=n;i>=1;i--) h2[i]=h2[i+1]*base+(s[i-1]-'a');
for(int i=1;i<=n;i++) h3[i]=h3[i-1]*base+(s2[i-1]-'a');
for(int i=n;i>=1;i--) h4[i]=h4[i+1]*base+(s2[i-1]-'a');
if(s[0]==s2[n-1]&&solve1(2,n)==solve2(2,n))
{
cout<<n+1<<endl;
return 0;
}
if(s2[0]==s[n-1]&&solve3(2,n)==solve4(2,n))
{
cout<<n+1<<endl;
return 0;
}
for(int i=1;i<=n;i++)
{
int l=1,r=min(i-1,n-i);
while(l<=r)
{
int mid=l+r>>1;
if(solve1(i-mid,i-1)==solve2(i+1,i+mid)) l=mid+1;
else r=mid-1;
}
int pos1=i-l+1,pos2=i+l-1;
l=1,r=min(pos1-1,n-pos2+1);
while(l<=r)
{
int mid=l+r>>1;
if(solve1(pos1-mid,pos1-1)==solve4(pos2,pos2+mid-1)) l=mid+1;
else r=mid-1;
}
if(pos1==pos2&&s[pos1-1]==s2[pos1-1])
{
int L=1,R=min(pos1-1,n-pos2);
while(L<=R)
{
int mid=L+R>>1;
if(solve1(pos1-mid,pos1-1)==solve4(pos2+1,pos2+mid)) L=mid+1;
else R=mid-1;
}
ans=max(ans,2*L);
}
pos1=pos1-l+1,pos2=pos2+l-1;
ans=max(ans,pos2-pos1+1);
if(i!=n&&s[i-1]==s[i])
{
l=1,r=min(i-1,n-i-1);
while(l<=r)
{
int mid=l+r>>1;
if(solve1(i-mid,i)==solve2(i+1,i+mid+1)) l=mid+1;
else r=mid-1;
}
pos1=i-l+1,pos2=i+l;
l=1,r=min(pos1-1,n-pos2+1);
while(l<=r)
{
int mid=l+r>>1;
if(solve1(pos1-mid,pos1-1)==solve4(pos2,pos2+mid-1)) l=mid+1;
else r=mid-1;
}
pos1=pos1-l+1,pos2=pos2+l-1;
ans=max(ans,pos2-pos1+1);
}
}
swap(s,s2);
reverse(s.begin(),s.end());
reverse(s2.begin(),s2.end());
for(int i=1;i<=n;i++) h1[i]=h1[i-1]*base+(s[i-1]-'a');
for(int i=n;i>=1;i--) h2[i]=h2[i+1]*base+(s[i-1]-'a');
for(int i=1;i<=n;i++) h3[i]=h3[i-1]*base+(s2[i-1]-'a');
for(int i=n;i>=1;i--) h4[i]=h4[i+1]*base+(s2[i-1]-'a');
for(int i=1;i<=n;i++)
{
int l=1,r=min(i-1,n-i);
while(l<=r)
{
int mid=l+r>>1;
if(solve1(i-mid,i-1)==solve2(i+1,i+mid)) l=mid+1;
else r=mid-1;
}
int pos1=i-l+1,pos2=i+l-1;
l=1,r=min(pos1-1,n-pos2+1);
while(l<=r)
{
int mid=l+r>>1;
if(solve1(pos1-mid,pos1-1)==solve4(pos2,pos2+mid-1)) l=mid+1;
else r=mid-1;
}
if(pos1==pos2&&s[pos1-1]==s2[pos1-1])
{
int L=1,R=min(pos1-1,n-pos2);
while(L<=R)
{
int mid=L+R>>1;
if(solve1(pos1-mid,pos1-1)==solve4(pos2+1,pos2+mid)) L=mid+1;
else R=mid-1;
}
ans=max(ans,2*L);
}
pos1=pos1-l+1,pos2=pos2+l-1;
ans=max(ans,pos2-pos1+1);
if(i!=n&&s[i]==s[i-1])
{
l=1,r=min(i-1,n-i-1);
while(l<=r)
{
int mid=l+r>>1;
if(solve1(i-mid,i)==solve2(i+1,i+mid+1)) l=mid+1;
else r=mid-1;
}
pos1=i-l+1,pos2=i+l;
l=1,r=min(pos1-1,n-pos2+1);
while(l<=r)
{
int mid=l+r>>1;
if(solve1(pos1-mid,pos1-1)==solve4(pos2,pos2+mid-1)) l=mid+1;
else r=mid-1;
}
pos1=pos1-l+1,pos2=pos2+l-1;
ans=max(ans,pos2-pos1+1);
}
}
cout<<ans<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 30
Accepted
Test #1:
score: 30
Accepted
time: 1ms
memory: 3592kb
input:
1000 mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...
output:
6
result:
ok single line: '6'
Test #2:
score: 30
Accepted
time: 1ms
memory: 3640kb
input:
1000 wvitzoxwlmhexjuqvoxksetoupgkhattucdzfevqorkdlsymjuvhobdrjsodtipwpfhipsdnyvqtsbbasrrvyybijzmpwseckztnpnkqswgkaeivflhwevhxcchjsnelqcixexkntwiuolsditpdwypgerzijziyrgqkwuucnqaehuwkpyrmwewjitvsaebyytznbtnkulnepceeloyjpfhcdpqfqhvzsmkcynjwztmkbnqaxnikfuiutocahdfbvsgdskgwqmzizzjlbqxnngftdohetabpjzpqzyc...
output:
7
result:
ok single line: '7'
Test #3:
score: 30
Accepted
time: 1ms
memory: 3792kb
input:
1000 abababaabaababbbbabbbbabbbbbbabbbaabbbaababaabaabbabbbbaabbaabaaaabbaaabbbbaaaaaabbbbababaababbaabbbbbbbbabbaababbbbabbaabbbabaaababbaababbbaabaabaababaaababbaaaababbbbbaaabbaabbaaabbaaaaabaaaaaabbbbbaaabbbbbaabbbbababaabaabbbbaaaaababaaaababbbbbbaababbbaaaababaabaabaabaaaaaabbabbabbbbbbbbbbabb...
output:
28
result:
ok single line: '28'
Test #4:
score: 30
Accepted
time: 1ms
memory: 3524kb
input:
1000 ababbababababbaababaaabaabaababbaabbbabaababbaaababbabbbbaabbababbbababbabababbaabbbaababbabaaaaabbbbbaaaaaaaaabbbbaabbbaabbababaaabababbaaaabababbbaabaabbabbaabaaaaaaabaaabaaababaaaababbaaabaabbbbbbaabbabaaabaabbbbabbababbbaaaaabbabbaabbaabbaabaaabaaabbbbbaabaaaaaababbbbbabbbabbbabababbbbbabaa...
output:
27
result:
ok single line: '27'
Test #5:
score: 30
Accepted
time: 0ms
memory: 3868kb
input:
1000 abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabba...
output:
987
result:
ok single line: '987'
Test #6:
score: 30
Accepted
time: 1ms
memory: 3572kb
input:
1000 aaaaaaababbabbabaabaaaaababaaaaaabaabaaaabaaaaaaabbbabaabbaaabaaaaaaabaaaaaaaabaaabbaababaaaaaaaaabbaabbabbaaaaabaaaaaaaabbaaabaaaaaaaaaaabaabbbbbaaaabaaaaaaaaabbbaaaaabaaabaaaaaaaaaaaaaababaaaaabbaabbaaaabaabaaaababaaaaaababaaaaabaaaaaaabaaaababaaaabbaaaabaaaaabaaaaaaaabaaaaaaabaaaaaaaaaaaabaa...
output:
45
result:
ok single line: '45'
Test #7:
score: 30
Accepted
time: 0ms
memory: 3652kb
input:
1000 aaaaaabaaaaaaaababaaaaaaababaaaabaabaaaaabaabaaaabbaaaaabaababaaaaaaaaaaabaaaabaaaaaaaaaaaaaaaaaabbaaaaaaababaabaaaabababaaaaabbaaaaaabbababaaabbaaababbaaaabbababaaaaaaaaabbbaaaababaaaaabaaaabbaabaaaaaabbaabaaaaaaaaaaabaaaababbaaaaaaaababbabaaaaaaaaabaaaabaaaaabaaaaaaaaaaaabaaaabaaababaabaabaab...
output:
45
result:
ok single line: '45'
Test #8:
score: 30
Accepted
time: 0ms
memory: 5820kb
input:
1000 aabaaaabaaaabaaabaabbbaabaabbbaaaaaaaaaabaaaaabaababaabaabaaaaaaaaaabbabbaaaaaaaabaabbbbbaaaabbabbbaaaaaabababbaaaabaaaaaaaaabaaaaaaaabaaaaaabbaaaaabaaaaaababaaababaaaabaaaaaabaaaaaaabaaaaabbaaaaabaababaaaabbaaabbaabaabaaaaababbababaaabbbabaabaaabaaabaababbabaababaaaaabaaababaaaaaaaaaabbaaaabaa...
output:
36
result:
ok single line: '36'
Test #9:
score: 30
Accepted
time: 1ms
memory: 3524kb
input:
1000 aaaaaabaabaaaaaaabaaaaaabaabaaaaaaaaabaabaaaaaaababaaaaabaaabaabaaabaaaaaaaaaaaaabbbbbabaaaaaaabaaaaabaaabaaaaabababaaabaaabaabaabaaaabbaabaaaaaaaaaaaaaaabbaaaaabaabbabbbaaabbbabaababbaabaaaabbaaaabaabbbaaaaaaaaaabaabaaaabbaaaabbbbaaabaaaaabaaababaaaaaaaaaabbabbabaaaaaaaaaaaaaaaabaababbaaaababa...
output:
50
result:
ok single line: '50'
Test #10:
score: 30
Accepted
time: 1ms
memory: 5668kb
input:
1000 aaccbdbabdaaddabaabaaaacbbccdbabbaacabcdababdcacadababaadaaaadabacababcdbaabaaaabdbabbdcaacccaaacababaacbcacaaabbabbaaabcbaaabaababbaaacbaacaaacabdccbbbaabaccacadbbcaabacadaababbaaabababbacaabbaaabcdaabaaaaaabaababaabcabacaabacaaaaaacaaabcbcabcbbcbbbaacaadadbadbbadcabababcabbcbbdadbdababaaadcab...
output:
20
result:
ok single line: '20'
Subtask #2:
score: 20
Accepted
Test #11:
score: 20
Accepted
time: 15ms
memory: 7540kb
input:
100000 ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...
output:
9
result:
ok single line: '9'
Test #12:
score: 20
Accepted
time: 15ms
memory: 7536kb
input:
100000 fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...
output:
9
result:
ok single line: '9'
Test #13:
score: 20
Accepted
time: 15ms
memory: 7824kb
input:
99999 biwnbsgdlxognjnepijlgbfbbahicjfqhdhcielcovdflacbrgcfapifaylqfmvipcccoofthuutfheboncacenchdgfljpidjbasdsikduidkbdqckmlnbfaidlincqkccbbpmnqnpbjoclgeduitraqmdfgdqinhddgberlbnlgggoafgqllbifekoccpgemcgdiiackkcfjgddhieabhzdjfwegcbuncdadebglitgwcbpmclfijmqtbbnbbrcehhanjgbddiaoimmkehtloreemecckjejifck...
output:
11
result:
ok single line: '11'
Test #14:
score: 20
Accepted
time: 15ms
memory: 7500kb
input:
99999 chgjcjipccsmclcpjqmbrcpaqdggbdodxbcejbklpjhkefeidkjojjjbljhtykbcdgnnjeictgjgliegyfilmlkqkgddpefibjusamblbpqfbbvcfkgfagikbujlbjvenjbmcadceadnltdeksatckmkjkscojeqbpaaglggxhideqhkhibchdasadfggcoihhcwlphbeevohhohtthepedqfggbdglidnatocrkhnkijraddqbesaiajimdhdmvbgodlcglqqmkeehcfabeaatjdinzhijewfoxhh...
output:
9
result:
ok single line: '9'
Test #15:
score: 20
Accepted
time: 14ms
memory: 7624kb
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: 9ms
memory: 7604kb
input:
100000 vucutyzmjlnyadjbpqkrlqvzuponzxrvqsqqgbemhzjftdkksfgspeuonmjwlbirvszhcafcxpeubixvxetwyyqmftbobhodwaiwrcwdvddohalyqgaatvpflorvjypszbvzpwiaxxgievaozquixcndkxqfxcxaiygyqcgdebogwzquvqfljgjcvvhpirfzqlkwctibngdsffpormliyhrkcbxwxoaoovaawldfenziwnlahllzhjsvdhzekcqekayusmvzrgsdiiymjxfiddhawhgxathvnsedf...
output:
10
result:
ok single line: '10'
Test #17:
score: 50
Accepted
time: 14ms
memory: 7496kb
input:
100000 fotxrzsqxuaaiiqmiymhtfdipylgdmxizgzqrgbrmdemonbisusgbmmsgtyoaqgdmxwoxayxkszpvpypzjoapilopvhyiyhckcccaalqriunudgfifgvdiufjtukpsmdfjjzftszwizrwoxuqsujchtrywpiiineoscbvarbalizfyydbctxpuwndzgshavpygfcmxkorbcppbatauqqkumaqsjcupnihewaukjajqgdvatobxjgdcbevlxpkjdvpofwtctivkexpwnbwvwbhcmlivuvifpptiupy...
output:
9
result:
ok single line: '9'
Test #18:
score: 50
Accepted
time: 24ms
memory: 7608kb
input:
100000 baaabababbbaabbbbaabbabbababbbbbaaaaabaabbbbbbaaabaabaaabababbabbabbaababbaababbbabaaaaabbbabbabaaaabaabbbbababaaaaabbbbbabbbababbbbbaaabbaaabaabaaababbababbabaaaaaaaababaaabaababbbababbbbabbbabaaababbababbbababaabbaabbabaaaabaaabbbabbaabbabbbbbbabbbbaaaaaaaaaaabbbaabaaaabbbabbbaabababbbbaabb...
output:
40
result:
ok single line: '40'
Test #19:
score: 50
Accepted
time: 24ms
memory: 7840kb
input:
100000 babbbbaabaaaaaaaaaabbbbababababababababbabaaabbaaaaabaaaabaaaaababaabaabaabbbbabbbaabababbbaaabaaaaaaababaabababababbaabbbaabaabbbbbbbabaabbaabaaaababbbaabaaabaaaabbabbababbaabbabbbaabbbaababbaabaabaabbabbbabaaaaaaaaaabaabbabaaaaababaabbababbbabababbbbabbbbababababaabbabbababbaababababbbbaaba...
output:
43
result:
ok single line: '43'
Test #20:
score: 50
Accepted
time: 26ms
memory: 7500kb
input:
100000 aabaabbaaaaabbbbbaaaaaaaaaaaaaabbaaaaaaaaabaaaabbaaaaaabaaaaabaabbaaabababaaabbaaaaaaaaaabbabbbaaaaaaabaaabbbaabaaabaaabaaaaaaaaaabaabaaaababaaaaaabbaaaaaaababaabaaaaabababaaaaaaaaaababaaaababbaaabaaaabaaaaabaababbaaaaabbaaabaabaabaaaaababaaaaabbaaaabaaaaaaabaaaaaaaaabaabaaaaaabaababbbabaaaba...
output:
75
result:
ok single line: '75'
Test #21:
score: 50
Accepted
time: 22ms
memory: 7628kb
input:
100000 aaaabaabaaabaabbaaaabbbaaaaaaabaabaabaabaaaababaaaaabaaaaabbabaabbaabaaaaaabaaaaaaaaaaaaabaabbabaaaaaabaaaaaaaaaaaabaaaabbbabaaaaaabaaaababaaaabaaaaaabbaaaaaaaaabababaaaaabaabababaaabbababaaaaababababbaaaaaabaabaaaabbababbbaaabaaaabaabaaaaabaabaaaaaabbbaaaaaaabababababbaaabaaabaaababaaaabaaaa...
output:
58
result:
ok single line: '58'
Test #22:
score: 50
Accepted
time: 22ms
memory: 7476kb
input:
100000 abbaaaaaaabaaaaaaaabaaaaaaaaaaaaaaaaabbabaaabaaaaaaaaaaaaaaabaaabbbaabaaaaabaaaaaaabaaaaabaabaabaaaababaaaaaaaaaaaaaaaaabaaabbabaaaaaaabaaaaaaabaaaaaabaaaaabaaabbaaaabbaabbaaababaababaaaaaabaaaaabaaaaaaaaaaaaababaaaaabaaaaaabbbabaaaaaaaaaaaaabaaaaaaaabbbaabaaabaaabaaabbabaabaaabbabaaaaaaaabba...
output:
67
result:
ok single line: '67'
Test #23:
score: 50
Accepted
time: 26ms
memory: 7620kb
input:
100000 bbaaaaabaaaaaaaaaabbaabaaaaaaabbbaabababaaababbaaaabaaaaaaaaaabaaaabbaaaaabaaaaaabbaabbbbaaabbaaaaaabbabaaabaababbaababaaabaaaaaaaaaabaaaaabbaaaaabbaaaabaaabababbbaabaaaaabaabaaaaaaabaaaaaaabaabababbbaaaaaaaaaaaaaaaaabaaaaaaabaaaaaababbbababaabaaabbbaaaaabaaaaaaabaabababaaaaaabaaaabbaabababaa...
output:
55
result:
ok single line: '55'
Test #24:
score: 50
Accepted
time: 21ms
memory: 7840kb
input:
100000 cabcacbbacbbaacbaabbaabbaabacdcadbbccabbccbbaabacacbabaccbaabbbaaabaddbcaccdcaababaaabbbbbcdacaabababcbbcbcabbbdbbbcadaadabcabbacabbdbbcaaabacaabbabbabacbabbabaadabbabdbabcbdcaacaddbbbabdabaaabcabcababbcbbaaccabbbbacaabbacdaaaabaaaaccaaabaaccbaccbbababdacaacabcaaabbaaacbcbaaabcaaabcaabbabbcad...
output:
25
result:
ok single line: '25'
Test #25:
score: 50
Accepted
time: 18ms
memory: 7792kb
input:
100000 abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbab...
output:
96421
result:
ok single line: '96421'
Test #26:
score: 50
Accepted
time: 0ms
memory: 3524kb
input:
5 pkusc pkukp
output:
6
result:
ok single line: '6'