QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#850814 | #8668. 回文路径 | erduolong | 100 ✓ | 35ms | 10912kb | C++14 | 1.5kb | 2025-01-10 12:01:00 | 2025-01-10 12:01:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+10,B='六';
typedef unsigned long long ULL;
char S[N],T[N];
char s[N];
ULL p[N],h[N];
int n;
int P(int i,int t)
{
if(t&1) return i+(t-1)*n;
else return n-i+1+(t-1)*n;
}
ULL get(int l,int r)
{
return h[r]-h[l-1]*p[r-l+1];
}
int Lcp(int i,int j,int mx)
{
if(mx<0) return -N;
int l=1,r=mx,ans=0;
while(l<=r)
{
int mid=l+r>>1;
if(get(i,i+mid-1)==get(j,j+mid-1)) ans=mid,l=mid+1;
else r=mid-1;
}
return ans;
}
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
p[0]=1;
for(int i=1;i<=n*4;i++) p[i]=p[i-1]*B;
cin>>(S+1);
cin>>(T+1);
for(int i=1;i<=n;i++) s[i]=S[i],s[i+n]=S[n-i+1],s[i+n*2]=T[i],s[i+n*3]=T[n-i+1];
for(int i=1;i<=n*4;i++) h[i]=h[i-1]*B+s[i];
int ans=0;
//at point
for(int i=1,x,l,r,mx,c,len;i<=n;i++)
{
x=Lcp(P(i,2),P(i,1),min(i,n-i+1)),len=x*2-1;
l=i-x,r=i+x;
c=Lcp(P(l,2),P(r-1,3),min(l,n-r+2));
ans=max(ans,len+c*2);
x=Lcp(P(i,4),P(i,3),min(i,n-i+1)),len=x*2-1;
l=i-x,r=i+x;
c=Lcp(P(l+1,2),P(r,3),min(l+1,n-r+1));
ans=max(ans,len+c*2);
}
//at edge
for(int i=1,x,l,r,mx,c,len;i<n;i++)
{
x=Lcp(P(i,2),P(i+1,1),min(i,n-i)),len=x*2;
l=i-x,r=i+1+x;
c=Lcp(P(l,2),P(r-1,3),min(l,n-r+2));
ans=max(ans,len+c*2);
x=Lcp(P(i,4),P(i+1,3),min(i,n-i)),len=x*2;
l=i-x,r=i+1+x;
c=Lcp(P(l+1,2),P(r,3),min(l+1,n-r+1));
ans=max(ans,len+c*2);
}
cout<<ans<<"\n";
return 0;
}
詳細信息
Subtask #1:
score: 30
Accepted
Test #1:
score: 30
Accepted
time: 1ms
memory: 7732kb
input:
1000 mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...
output:
6
result:
ok single line: '6'
Test #2:
score: 30
Accepted
time: 0ms
memory: 7704kb
input:
1000 wvitzoxwlmhexjuqvoxksetoupgkhattucdzfevqorkdlsymjuvhobdrjsodtipwpfhipsdnyvqtsbbasrrvyybijzmpwseckztnpnkqswgkaeivflhwevhxcchjsnelqcixexkntwiuolsditpdwypgerzijziyrgqkwuucnqaehuwkpyrmwewjitvsaebyytznbtnkulnepceeloyjpfhcdpqfqhvzsmkcynjwztmkbnqaxnikfuiutocahdfbvsgdskgwqmzizzjlbqxnngftdohetabpjzpqzyc...
output:
7
result:
ok single line: '7'
Test #3:
score: 30
Accepted
time: 1ms
memory: 7768kb
input:
1000 abababaabaababbbbabbbbabbbbbbabbbaabbbaababaabaabbabbbbaabbaabaaaabbaaabbbbaaaaaabbbbababaababbaabbbbbbbbabbaababbbbabbaabbbabaaababbaababbbaabaabaababaaababbaaaababbbbbaaabbaabbaaabbaaaaabaaaaaabbbbbaaabbbbbaabbbbababaabaabbbbaaaaababaaaababbbbbbaababbbaaaababaabaabaabaaaaaabbabbabbbbbbbbbbabb...
output:
28
result:
ok single line: '28'
Test #4:
score: 30
Accepted
time: 0ms
memory: 7716kb
input:
1000 ababbababababbaababaaabaabaababbaabbbabaababbaaababbabbbbaabbababbbababbabababbaabbbaababbabaaaaabbbbbaaaaaaaaabbbbaabbbaabbababaaabababbaaaabababbbaabaabbabbaabaaaaaaabaaabaaababaaaababbaaabaabbbbbbaabbabaaabaabbbbabbababbbaaaaabbabbaabbaabbaabaaabaaabbbbbaabaaaaaababbbbbabbbabbbabababbbbbabaa...
output:
27
result:
ok single line: '27'
Test #5:
score: 30
Accepted
time: 1ms
memory: 5752kb
input:
1000 abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabba...
output:
987
result:
ok single line: '987'
Test #6:
score: 30
Accepted
time: 2ms
memory: 7832kb
input:
1000 aaaaaaababbabbabaabaaaaababaaaaaabaabaaaabaaaaaaabbbabaabbaaabaaaaaaabaaaaaaaabaaabbaababaaaaaaaaabbaabbabbaaaaabaaaaaaaabbaaabaaaaaaaaaaabaabbbbbaaaabaaaaaaaaabbbaaaaabaaabaaaaaaaaaaaaaababaaaaabbaabbaaaabaabaaaababaaaaaababaaaaabaaaaaaabaaaababaaaabbaaaabaaaaabaaaaaaaabaaaaaaabaaaaaaaaaaaabaa...
output:
45
result:
ok single line: '45'
Test #7:
score: 30
Accepted
time: 0ms
memory: 7792kb
input:
1000 aaaaaabaaaaaaaababaaaaaaababaaaabaabaaaaabaabaaaabbaaaaabaababaaaaaaaaaaabaaaabaaaaaaaaaaaaaaaaaabbaaaaaaababaabaaaabababaaaaabbaaaaaabbababaaabbaaababbaaaabbababaaaaaaaaabbbaaaababaaaaabaaaabbaabaaaaaabbaabaaaaaaaaaaabaaaababbaaaaaaaababbabaaaaaaaaabaaaabaaaaabaaaaaaaaaaaabaaaabaaababaabaabaab...
output:
45
result:
ok single line: '45'
Test #8:
score: 30
Accepted
time: 1ms
memory: 5676kb
input:
1000 aabaaaabaaaabaaabaabbbaabaabbbaaaaaaaaaabaaaaabaababaabaabaaaaaaaaaabbabbaaaaaaaabaabbbbbaaaabbabbbaaaaaabababbaaaabaaaaaaaaabaaaaaaaabaaaaaabbaaaaabaaaaaababaaababaaaabaaaaaabaaaaaaabaaaaabbaaaaabaababaaaabbaaabbaabaabaaaaababbababaaabbbabaabaaabaaabaababbabaababaaaaabaaababaaaaaaaaaabbaaaabaa...
output:
36
result:
ok single line: '36'
Test #9:
score: 30
Accepted
time: 1ms
memory: 7712kb
input:
1000 aaaaaabaabaaaaaaabaaaaaabaabaaaaaaaaabaabaaaaaaababaaaaabaaabaabaaabaaaaaaaaaaaaabbbbbabaaaaaaabaaaaabaaabaaaaabababaaabaaabaabaabaaaabbaabaaaaaaaaaaaaaaabbaaaaabaabbabbbaaabbbabaababbaabaaaabbaaaabaabbbaaaaaaaaaabaabaaaabbaaaabbbbaaabaaaaabaaababaaaaaaaaaabbabbabaaaaaaaaaaaaaaaabaababbaaaababa...
output:
50
result:
ok single line: '50'
Test #10:
score: 30
Accepted
time: 1ms
memory: 5804kb
input:
1000 aaccbdbabdaaddabaabaaaacbbccdbabbaacabcdababdcacadababaadaaaadabacababcdbaabaaaabdbabbdcaacccaaacababaacbcacaaabbabbaaabcbaaabaababbaaacbaacaaacabdccbbbaabaccacadbbcaabacadaababbaaabababbacaabbaaabcdaabaaaaaabaababaabcabacaabacaaaaaacaaabcbcabcbbcbbbaacaadadbadbbadcabababcabbcbbdadbdababaaadcab...
output:
20
result:
ok single line: '20'
Subtask #2:
score: 20
Accepted
Test #11:
score: 20
Accepted
time: 30ms
memory: 10500kb
input:
100000 ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...
output:
9
result:
ok single line: '9'
Test #12:
score: 20
Accepted
time: 25ms
memory: 10504kb
input:
100000 fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...
output:
9
result:
ok single line: '9'
Test #13:
score: 20
Accepted
time: 25ms
memory: 10788kb
input:
99999 biwnbsgdlxognjnepijlgbfbbahicjfqhdhcielcovdflacbrgcfapifaylqfmvipcccoofthuutfheboncacenchdgfljpidjbasdsikduidkbdqckmlnbfaidlincqkccbbpmnqnpbjoclgeduitraqmdfgdqinhddgberlbnlgggoafgqllbifekoccpgemcgdiiackkcfjgddhieabhzdjfwegcbuncdadebglitgwcbpmclfijmqtbbnbbrcehhanjgbddiaoimmkehtloreemecckjejifck...
output:
11
result:
ok single line: '11'
Test #14:
score: 20
Accepted
time: 25ms
memory: 10488kb
input:
99999 chgjcjipccsmclcpjqmbrcpaqdggbdodxbcejbklpjhkefeidkjojjjbljhtykbcdgnnjeictgjgliegyfilmlkqkgddpefibjusamblbpqfbbvcfkgfagikbujlbjvenjbmcadceadnltdeksatckmkjkscojeqbpaaglggxhideqhkhibchdasadfggcoihhcwlphbeevohhohtthepedqfggbdglidnatocrkhnkijraddqbesaiajimdhdmvbgodlcglqqmkeehcfabeaatjdinzhijewfoxhh...
output:
9
result:
ok single line: '9'
Test #15:
score: 20
Accepted
time: 23ms
memory: 10716kb
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: 24ms
memory: 10696kb
input:
100000 vucutyzmjlnyadjbpqkrlqvzuponzxrvqsqqgbemhzjftdkksfgspeuonmjwlbirvszhcafcxpeubixvxetwyyqmftbobhodwaiwrcwdvddohalyqgaatvpflorvjypszbvzpwiaxxgievaozquixcndkxqfxcxaiygyqcgdebogwzquvqfljgjcvvhpirfzqlkwctibngdsffpormliyhrkcbxwxoaoovaawldfenziwnlahllzhjsvdhzekcqekayusmvzrgsdiiymjxfiddhawhgxathvnsedf...
output:
10
result:
ok single line: '10'
Test #17:
score: 50
Accepted
time: 26ms
memory: 10492kb
input:
100000 fotxrzsqxuaaiiqmiymhtfdipylgdmxizgzqrgbrmdemonbisusgbmmsgtyoaqgdmxwoxayxkszpvpypzjoapilopvhyiyhckcccaalqriunudgfifgvdiufjtukpsmdfjjzftszwizrwoxuqsujchtrywpiiineoscbvarbalizfyydbctxpuwndzgshavpygfcmxkorbcppbatauqqkumaqsjcupnihewaukjajqgdvatobxjgdcbevlxpkjdvpofwtctivkexpwnbwvwbhcmlivuvifpptiupy...
output:
9
result:
ok single line: '9'
Test #18:
score: 50
Accepted
time: 34ms
memory: 10912kb
input:
100000 baaabababbbaabbbbaabbabbababbbbbaaaaabaabbbbbbaaabaabaaabababbabbabbaababbaababbbabaaaaabbbabbabaaaabaabbbbababaaaaabbbbbabbbababbbbbaaabbaaabaabaaababbababbabaaaaaaaababaaabaababbbababbbbabbbabaaababbababbbababaabbaabbabaaaabaaabbbabbaabbabbbbbbabbbbaaaaaaaaaaabbbaabaaaabbbabbbaabababbbbaabb...
output:
40
result:
ok single line: '40'
Test #19:
score: 50
Accepted
time: 31ms
memory: 10504kb
input:
100000 babbbbaabaaaaaaaaaabbbbababababababababbabaaabbaaaaabaaaabaaaaababaabaabaabbbbabbbaabababbbaaabaaaaaaababaabababababbaabbbaabaabbbbbbbabaabbaabaaaababbbaabaaabaaaabbabbababbaabbabbbaabbbaababbaabaabaabbabbbabaaaaaaaaaabaabbabaaaaababaabbababbbabababbbbabbbbababababaabbabbababbaababababbbbaaba...
output:
43
result:
ok single line: '43'
Test #20:
score: 50
Accepted
time: 31ms
memory: 10760kb
input:
100000 aabaabbaaaaabbbbbaaaaaaaaaaaaaabbaaaaaaaaabaaaabbaaaaaabaaaaabaabbaaabababaaabbaaaaaaaaaabbabbbaaaaaaabaaabbbaabaaabaaabaaaaaaaaaabaabaaaababaaaaaabbaaaaaaababaabaaaaabababaaaaaaaaaababaaaababbaaabaaaabaaaaabaababbaaaaabbaaabaabaabaaaaababaaaaabbaaaabaaaaaaabaaaaaaaaabaabaaaaaabaababbbabaaaba...
output:
75
result:
ok single line: '75'
Test #21:
score: 50
Accepted
time: 35ms
memory: 10732kb
input:
100000 aaaabaabaaabaabbaaaabbbaaaaaaabaabaabaabaaaababaaaaabaaaaabbabaabbaabaaaaaabaaaaaaaaaaaaabaabbabaaaaaabaaaaaaaaaaaabaaaabbbabaaaaaabaaaababaaaabaaaaaabbaaaaaaaaabababaaaaabaabababaaabbababaaaaababababbaaaaaabaabaaaabbababbbaaabaaaabaabaaaaabaabaaaaaabbbaaaaaaabababababbaaabaaabaaababaaaabaaaa...
output:
58
result:
ok single line: '58'
Test #22:
score: 50
Accepted
time: 32ms
memory: 10468kb
input:
100000 abbaaaaaaabaaaaaaaabaaaaaaaaaaaaaaaaabbabaaabaaaaaaaaaaaaaaabaaabbbaabaaaaabaaaaaaabaaaaabaabaabaaaababaaaaaaaaaaaaaaaaabaaabbabaaaaaaabaaaaaaabaaaaaabaaaaabaaabbaaaabbaabbaaababaababaaaaaabaaaaabaaaaaaaaaaaaababaaaaabaaaaaabbbabaaaaaaaaaaaaabaaaaaaaabbbaabaaabaaabaaabbabaabaaabbabaaaaaaaabba...
output:
67
result:
ok single line: '67'
Test #23:
score: 50
Accepted
time: 35ms
memory: 10552kb
input:
100000 bbaaaaabaaaaaaaaaabbaabaaaaaaabbbaabababaaababbaaaabaaaaaaaaaabaaaabbaaaaabaaaaaabbaabbbbaaabbaaaaaabbabaaabaababbaababaaabaaaaaaaaaabaaaaabbaaaaabbaaaabaaabababbbaabaaaaabaabaaaaaaabaaaaaaabaabababbbaaaaaaaaaaaaaaaaabaaaaaaabaaaaaababbbababaabaaabbbaaaaabaaaaaaabaabababaaaaaabaaaabbaabababaa...
output:
55
result:
ok single line: '55'
Test #24:
score: 50
Accepted
time: 28ms
memory: 10508kb
input:
100000 cabcacbbacbbaacbaabbaabbaabacdcadbbccabbccbbaabacacbabaccbaabbbaaabaddbcaccdcaababaaabbbbbcdacaabababcbbcbcabbbdbbbcadaadabcabbacabbdbbcaaabacaabbabbabacbabbabaadabbabdbabcbdcaacaddbbbabdabaaabcabcababbcbbaaccabbbbacaabbacdaaaabaaaaccaaabaaccbaccbbababdacaacabcaaabbaaacbcbaaabcaaabcaabbabbcad...
output:
25
result:
ok single line: '25'
Test #25:
score: 50
Accepted
time: 26ms
memory: 10504kb
input:
100000 abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbab...
output:
96421
result:
ok single line: '96421'
Test #26:
score: 50
Accepted
time: 1ms
memory: 5704kb
input:
5 pkusc pkukp
output:
6
result:
ok single line: '6'