QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #819721 | #8668. 回文路径 | DerrickLo | 100 ✓ | 77ms | 13428kb | C++14 | 3.2kb | 2024-12-18 17:13:17 | 2024-12-18 17:13:17 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans;
string s[3];
class Hash{
public:
#define mod1 998244853
#define mod2 1000000009
#define base1 1331
#define base2 3113
int hs1[100005],hs2[100005],hs3[100005],hs4[100005],pw1[100005],pw2[100005];
void init(int n,string&s){
pw1[0]=pw2[0]=1,hs3[n+1]=hs4[n+1]=0;
for(int i=1;i<=n;i++)pw1[i]=pw1[i-1]*base1%mod1;
for(int i=1;i<=n;i++)pw2[i]=pw2[i-1]*base2%mod2;
for(int i=1;i<=n;i++)hs1[i]=hs1[i-1]*base1+s[i],hs1[i]%=mod1;
for(int i=1;i<=n;i++)hs2[i]=hs2[i-1]*base2+s[i],hs2[i]%=mod2;
for(int i=n;i;i--)hs3[i]=hs3[i+1]*base1+s[i],hs3[i]%=mod1;
for(int i=n;i;i--)hs4[i]=hs4[i+1]*base2+s[i],hs4[i]%=mod2;
}
int qry1(int l,int r){
return(hs1[r]-hs1[l-1]*pw1[r-l+1]%mod1+mod1)%mod1;
}
int qry2(int l,int r){
return(hs2[r]-hs2[l-1]*pw2[r-l+1]%mod2+mod2)%mod2;
}
int uqry1(int l,int r){
return(hs3[l]-hs3[r+1]*pw1[r-l+1]%mod1+mod1)%mod1;
}
int uqry2(int l,int r){
return(hs4[l]-hs4[r+1]*pw2[r-l+1]%mod2+mod2)%mod2;
}
bool pal(int l,int r){
return qry1(l,r)==uqry1(l,r)&&qry2(l,r)==uqry2(l,r);
}
}hs1,hs2;
signed main(){
cin>>n>>s[1]>>s[2],s[1]=" "+s[1],s[2]=" "+s[2];
hs1.init(n,s[1]),hs2.init(n,s[2]);
for(int i=1;i<=n;i++){
int l=1,r=min(i,n-i+1),anss=0;
while(l<=r){
int mid=l+r>>1;
if(hs1.pal(i-mid+1,i+mid-1))anss=mid,l=mid+1;
else r=mid-1;
}
if(anss==i){ans=max(ans,2*i-1);continue;}
int ll=i-anss,rr=i+anss-1,noww=anss;
l=1,r=min(ll,n-rr+1),anss=0;
while(l<=r){
int mid=l+r>>1;
if(hs1.qry1(ll-mid+1,ll)==hs2.uqry1(rr,rr+mid-1)&&hs1.qry2(ll-mid+1,ll)==hs2.uqry2(rr,rr+mid-1))anss=mid,l=mid+1;
else r=mid-1;
}
noww+=anss,ans=max(ans,2*noww-1);
}
for(int i=1;i<=n;i++){
int l=1,r=min(i,n-i+1),anss=0;
while(l<=r){
int mid=l+r>>1;
if(hs1.pal(i-mid+1,i+mid))anss=mid,l=mid+1;
else r=mid-1;
}
if(anss==i){ans=max(ans,2*i);continue;}
int ll=i-anss,rr=i+anss,noww=anss;
l=1,r=min(ll,n-rr+1),anss=0;
while(l<=r){
int mid=l+r>>1;
if(hs1.qry1(ll-mid+1,ll)==hs2.uqry1(rr,rr+mid-1)&&hs1.qry2(ll-mid+1,ll)==hs2.uqry2(rr,rr+mid-1))anss=mid,l=mid+1;
else r=mid-1;
}
noww+=anss,ans=max(ans,2*noww);
}
for(int i=1;i<=n;i++){
int l=1,r=min(i,n-i+1),anss=0;
while(l<=r){
int mid=l+r>>1;
if(hs2.pal(i-mid+1,i+mid-1))anss=mid,l=mid+1;
else r=mid-1;
}
if(anss==n-i+1){ans=max(ans,2*(n-i+1)-1);continue;}
int ll=i-anss+1,rr=i+anss,noww=anss;
l=1,r=min(ll,n-rr+1),anss=0;
while(l<=r){
int mid=l+r>>1;
if(hs1.qry1(ll-mid+1,ll)==hs2.uqry1(rr,rr+mid-1)&&hs1.qry2(ll-mid+1,ll)==hs2.uqry2(rr,rr+mid-1))anss=mid,l=mid+1;
else r=mid-1;
}
noww+=anss,ans=max(ans,2*noww-1);
}
for(int i=1;i<=n;i++){
int l=1,r=min(i,n-i+1),anss=0;
while(l<=r){
int mid=l+r>>1;
if(hs2.pal(i-mid,i+mid-1))anss=mid,l=mid+1;
else r=mid-1;
}
if(anss==n-i+1){ans=max(ans,2*(n-i+1));continue;}
int ll=i-anss,rr=i+anss,noww=anss;
l=1,r=min(ll,n-rr+1),anss=0;
while(l<=r){
int mid=l+r>>1;
if(hs1.qry1(ll-mid+1,ll)==hs2.uqry1(rr,rr+mid-1)&&hs1.qry2(ll-mid+1,ll)==hs2.uqry2(rr,rr+mid-1))anss=mid,l=mid+1;
else r=mid-1;
}
noww+=anss,ans=max(ans,2*noww);
}
cout<<ans;
return 0;
}
详细
Subtask #1:
score: 30
Accepted
Test #1:
score: 30
Accepted
time: 0ms
memory: 7812kb
input:
1000 mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...
output:
6
result:
ok single line: '6'
Test #2:
score: 30
Accepted
time: 1ms
memory: 7796kb
input:
1000 wvitzoxwlmhexjuqvoxksetoupgkhattucdzfevqorkdlsymjuvhobdrjsodtipwpfhipsdnyvqtsbbasrrvyybijzmpwseckztnpnkqswgkaeivflhwevhxcchjsnelqcixexkntwiuolsditpdwypgerzijziyrgqkwuucnqaehuwkpyrmwewjitvsaebyytznbtnkulnepceeloyjpfhcdpqfqhvzsmkcynjwztmkbnqaxnikfuiutocahdfbvsgdskgwqmzizzjlbqxnngftdohetabpjzpqzyc...
output:
7
result:
ok single line: '7'
Test #3:
score: 30
Accepted
time: 0ms
memory: 10000kb
input:
1000 abababaabaababbbbabbbbabbbbbbabbbaabbbaababaabaabbabbbbaabbaabaaaabbaaabbbbaaaaaabbbbababaababbaabbbbbbbbabbaababbbbabbaabbbabaaababbaababbbaabaabaababaaababbaaaababbbbbaaabbaabbaaabbaaaaabaaaaaabbbbbaaabbbbbaabbbbababaabaabbbbaaaaababaaaababbbbbbaababbbaaaababaabaabaabaaaaaabbabbabbbbbbbbbbabb...
output:
28
result:
ok single line: '28'
Test #4:
score: 30
Accepted
time: 2ms
memory: 11760kb
input:
1000 ababbababababbaababaaabaabaababbaabbbabaababbaaababbabbbbaabbababbbababbabababbaabbbaababbabaaaaabbbbbaaaaaaaaabbbbaabbbaabbababaaabababbaaaabababbbaabaabbabbaabaaaaaaabaaabaaababaaaababbaaabaabbbbbbaabbabaaabaabbbbabbababbbaaaaabbabbaabbaabbaabaaabaaabbbbbaabaaaaaababbbbbabbbabbbabababbbbbabaa...
output:
27
result:
ok single line: '27'
Test #5:
score: 30
Accepted
time: 1ms
memory: 7716kb
input:
1000 abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabba...
output:
987
result:
ok single line: '987'
Test #6:
score: 30
Accepted
time: 2ms
memory: 7800kb
input:
1000 aaaaaaababbabbabaabaaaaababaaaaaabaabaaaabaaaaaaabbbabaabbaaabaaaaaaabaaaaaaaabaaabbaababaaaaaaaaabbaabbabbaaaaabaaaaaaaabbaaabaaaaaaaaaaabaabbbbbaaaabaaaaaaaaabbbaaaaabaaabaaaaaaaaaaaaaababaaaaabbaabbaaaabaabaaaababaaaaaababaaaaabaaaaaaabaaaababaaaabbaaaabaaaaabaaaaaaaabaaaaaaabaaaaaaaaaaaabaa...
output:
45
result:
ok single line: '45'
Test #7:
score: 30
Accepted
time: 2ms
memory: 8028kb
input:
1000 aaaaaabaaaaaaaababaaaaaaababaaaabaabaaaaabaabaaaabbaaaaabaababaaaaaaaaaaabaaaabaaaaaaaaaaaaaaaaaabbaaaaaaababaabaaaabababaaaaabbaaaaaabbababaaabbaaababbaaaabbababaaaaaaaaabbbaaaababaaaaabaaaabbaabaaaaaabbaabaaaaaaaaaaabaaaababbaaaaaaaababbabaaaaaaaaabaaaabaaaaabaaaaaaaaaaaabaaaabaaababaabaabaab...
output:
45
result:
ok single line: '45'
Test #8:
score: 30
Accepted
time: 2ms
memory: 8016kb
input:
1000 aabaaaabaaaabaaabaabbbaabaabbbaaaaaaaaaabaaaaabaababaabaabaaaaaaaaaabbabbaaaaaaaabaabbbbbaaaabbabbbaaaaaabababbaaaabaaaaaaaaabaaaaaaaabaaaaaabbaaaaabaaaaaababaaababaaaabaaaaaabaaaaaaabaaaaabbaaaaabaababaaaabbaaabbaabaabaaaaababbababaaabbbabaabaaabaaabaababbabaababaaaaabaaababaaaaaaaaaabbaaaabaa...
output:
36
result:
ok single line: '36'
Test #9:
score: 30
Accepted
time: 0ms
memory: 8020kb
input:
1000 aaaaaabaabaaaaaaabaaaaaabaabaaaaaaaaabaabaaaaaaababaaaaabaaabaabaaabaaaaaaaaaaaaabbbbbabaaaaaaabaaaaabaaabaaaaabababaaabaaabaabaabaaaabbaabaaaaaaaaaaaaaaabbaaaaabaabbabbbaaabbbabaababbaabaaaabbaaaabaabbbaaaaaaaaaabaabaaaabbaaaabbbbaaabaaaaabaaababaaaaaaaaaabbabbabaaaaaaaaaaaaaaaabaababbaaaababa...
output:
50
result:
ok single line: '50'
Test #10:
score: 30
Accepted
time: 0ms
memory: 9808kb
input:
1000 aaccbdbabdaaddabaabaaaacbbccdbabbaacabcdababdcacadababaadaaaadabacababcdbaabaaaabdbabbdcaacccaaacababaacbcacaaabbabbaaabcbaaabaababbaaacbaacaaacabdccbbbaabaccacadbbcaabacadaababbaaabababbacaabbaaabcdaabaaaaaabaababaabcabacaabacaaaaaacaaabcbcabcbbcbbbaacaadadbadbbadcabababcabbcbbdadbdababaaadcab...
output:
20
result:
ok single line: '20'
Subtask #2:
score: 20
Accepted
Test #11:
score: 20
Accepted
time: 60ms
memory: 13132kb
input:
100000 ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...
output:
9
result:
ok single line: '9'
Test #12:
score: 20
Accepted
time: 67ms
memory: 13428kb
input:
100000 fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...
output:
9
result:
ok single line: '9'
Test #13:
score: 20
Accepted
time: 69ms
memory: 13128kb
input:
99999 biwnbsgdlxognjnepijlgbfbbahicjfqhdhcielcovdflacbrgcfapifaylqfmvipcccoofthuutfheboncacenchdgfljpidjbasdsikduidkbdqckmlnbfaidlincqkccbbpmnqnpbjoclgeduitraqmdfgdqinhddgberlbnlgggoafgqllbifekoccpgemcgdiiackkcfjgddhieabhzdjfwegcbuncdadebglitgwcbpmclfijmqtbbnbbrcehhanjgbddiaoimmkehtloreemecckjejifck...
output:
11
result:
ok single line: '11'
Test #14:
score: 20
Accepted
time: 63ms
memory: 13200kb
input:
99999 chgjcjipccsmclcpjqmbrcpaqdggbdodxbcejbklpjhkefeidkjojjjbljhtykbcdgnnjeictgjgliegyfilmlkqkgddpefibjusamblbpqfbbvcfkgfagikbujlbjvenjbmcadceadnltdeksatckmkjkscojeqbpaaglggxhideqhkhibchdasadfggcoihhcwlphbeevohhohtthepedqfggbdglidnatocrkhnkijraddqbesaiajimdhdmvbgodlcglqqmkeehcfabeaatjdinzhijewfoxhh...
output:
9
result:
ok single line: '9'
Test #15:
score: 20
Accepted
time: 61ms
memory: 13388kb
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: 63ms
memory: 13228kb
input:
100000 vucutyzmjlnyadjbpqkrlqvzuponzxrvqsqqgbemhzjftdkksfgspeuonmjwlbirvszhcafcxpeubixvxetwyyqmftbobhodwaiwrcwdvddohalyqgaatvpflorvjypszbvzpwiaxxgievaozquixcndkxqfxcxaiygyqcgdebogwzquvqfljgjcvvhpirfzqlkwctibngdsffpormliyhrkcbxwxoaoovaawldfenziwnlahllzhjsvdhzekcqekayusmvzrgsdiiymjxfiddhawhgxathvnsedf...
output:
10
result:
ok single line: '10'
Test #17:
score: 50
Accepted
time: 63ms
memory: 13164kb
input:
100000 fotxrzsqxuaaiiqmiymhtfdipylgdmxizgzqrgbrmdemonbisusgbmmsgtyoaqgdmxwoxayxkszpvpypzjoapilopvhyiyhckcccaalqriunudgfifgvdiufjtukpsmdfjjzftszwizrwoxuqsujchtrywpiiineoscbvarbalizfyydbctxpuwndzgshavpygfcmxkorbcppbatauqqkumaqsjcupnihewaukjajqgdvatobxjgdcbevlxpkjdvpofwtctivkexpwnbwvwbhcmlivuvifpptiupy...
output:
9
result:
ok single line: '9'
Test #18:
score: 50
Accepted
time: 76ms
memory: 13188kb
input:
100000 baaabababbbaabbbbaabbabbababbbbbaaaaabaabbbbbbaaabaabaaabababbabbabbaababbaababbbabaaaaabbbabbabaaaabaabbbbababaaaaabbbbbabbbababbbbbaaabbaaabaabaaababbababbabaaaaaaaababaaabaababbbababbbbabbbabaaababbababbbababaabbaabbabaaaabaaabbbabbaabbabbbbbbabbbbaaaaaaaaaaabbbaabaaaabbbabbbaabababbbbaabb...
output:
40
result:
ok single line: '40'
Test #19:
score: 50
Accepted
time: 71ms
memory: 13168kb
input:
100000 babbbbaabaaaaaaaaaabbbbababababababababbabaaabbaaaaabaaaabaaaaababaabaabaabbbbabbbaabababbbaaabaaaaaaababaabababababbaabbbaabaabbbbbbbabaabbaabaaaababbbaabaaabaaaabbabbababbaabbabbbaabbbaababbaabaabaabbabbbabaaaaaaaaaabaabbabaaaaababaabbababbbabababbbbabbbbababababaabbabbababbaababababbbbaaba...
output:
43
result:
ok single line: '43'
Test #20:
score: 50
Accepted
time: 77ms
memory: 13228kb
input:
100000 aabaabbaaaaabbbbbaaaaaaaaaaaaaabbaaaaaaaaabaaaabbaaaaaabaaaaabaabbaaabababaaabbaaaaaaaaaabbabbbaaaaaaabaaabbbaabaaabaaabaaaaaaaaaabaabaaaababaaaaaabbaaaaaaababaabaaaaabababaaaaaaaaaababaaaababbaaabaaaabaaaaabaababbaaaaabbaaabaabaabaaaaababaaaaabbaaaabaaaaaaabaaaaaaaaabaabaaaaaabaababbbabaaaba...
output:
75
result:
ok single line: '75'
Test #21:
score: 50
Accepted
time: 69ms
memory: 13188kb
input:
100000 aaaabaabaaabaabbaaaabbbaaaaaaabaabaabaabaaaababaaaaabaaaaabbabaabbaabaaaaaabaaaaaaaaaaaaabaabbabaaaaaabaaaaaaaaaaaabaaaabbbabaaaaaabaaaababaaaabaaaaaabbaaaaaaaaabababaaaaabaabababaaabbababaaaaababababbaaaaaabaabaaaabbababbbaaabaaaabaabaaaaabaabaaaaaabbbaaaaaaabababababbaaabaaabaaababaaaabaaaa...
output:
58
result:
ok single line: '58'
Test #22:
score: 50
Accepted
time: 77ms
memory: 13192kb
input:
100000 abbaaaaaaabaaaaaaaabaaaaaaaaaaaaaaaaabbabaaabaaaaaaaaaaaaaaabaaabbbaabaaaaabaaaaaaabaaaaabaabaabaaaababaaaaaaaaaaaaaaaaabaaabbabaaaaaaabaaaaaaabaaaaaabaaaaabaaabbaaaabbaabbaaababaababaaaaaabaaaaabaaaaaaaaaaaaababaaaaabaaaaaabbbabaaaaaaaaaaaaabaaaaaaaabbbaabaaabaaabaaabbabaabaaabbabaaaaaaaabba...
output:
67
result:
ok single line: '67'
Test #23:
score: 50
Accepted
time: 74ms
memory: 13416kb
input:
100000 bbaaaaabaaaaaaaaaabbaabaaaaaaabbbaabababaaababbaaaabaaaaaaaaaabaaaabbaaaaabaaaaaabbaabbbbaaabbaaaaaabbabaaabaababbaababaaabaaaaaaaaaabaaaaabbaaaaabbaaaabaaabababbbaabaaaaabaabaaaaaaabaaaaaaabaabababbbaaaaaaaaaaaaaaaaabaaaaaaabaaaaaababbbababaabaaabbbaaaaabaaaaaaabaabababaaaaaabaaaabbaabababaa...
output:
55
result:
ok single line: '55'
Test #24:
score: 50
Accepted
time: 72ms
memory: 13196kb
input:
100000 cabcacbbacbbaacbaabbaabbaabacdcadbbccabbccbbaabacacbabaccbaabbbaaabaddbcaccdcaababaaabbbbbcdacaabababcbbcbcabbbdbbbcadaadabcabbacabbdbbcaaabacaabbabbabacbabbabaadabbabdbabcbdcaacaddbbbabdabaaabcabcababbcbbaaccabbbbacaabbacdaaaabaaaaccaaabaaccbaccbbababdacaacabcaaabbaaacbcbaaabcaaabcaabbabbcad...
output:
25
result:
ok single line: '25'
Test #25:
score: 50
Accepted
time: 68ms
memory: 13188kb
input:
100000 abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbab...
output:
96421
result:
ok single line: '96421'
Test #26:
score: 50
Accepted
time: 0ms
memory: 9768kb
input:
5 pkusc pkukp
output:
6
result:
ok single line: '6'