QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#557233 | #8668. 回文路径 | AllenJYL | 100 ✓ | 77ms | 7996kb | C++14 | 4.5kb | 2024-09-11 08:20:17 | 2024-09-11 08:20:17 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
// #define ls p<<1
// #define rs p<<1|1
#define msp(_array) memset(_array,0x3f,sizeof _array)
#define ms0(_array) memset(_array,0,sizeof _array)
#define msn(_array) memset(_array,-1,sizeof _array)
#define mc(_tar,_array) memcpy(_tar,_array,sizeof _tar)
#define pii pair<int,int>
#define endl '\n'
bool bg_memory;
const int mod=1226999999;
const int inf=2147483647;
const int bs=23333;
const double eps=1e-6;
const int N=1e5+7,M=1e5+7;
inline void cmax(int &a,int b){a=a<b?b:a;}
inline void cmin(int &a,int b){a=a>b?b:a;}
inline int qp(int a,int b){int res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
int n;
string s,t;
int hs[N],ht[N],rhs[N],rht[N];
int pw[N];
int ans;
mt19937 rnd(time(0));
int Case=1;
void Main(){
cin>>n>>s>>t;
s=' '+s;
t=' '+t;
pw[0]=1;
for(int i=1;i<=n;i++) pw[i]=pw[i-1]*bs%mod;
for(int i=1;i<=n;i++) hs[i]=(hs[i-1]*bs%mod+s[i])%mod;
for(int i=1;i<=n;i++) ht[i]=(ht[i-1]*bs%mod+t[i])%mod;
for(int i=n;i>=1;i--) rhs[i]=(rhs[i+1]*bs%mod+s[i])%mod;
for(int i=n;i>=1;i--) rht[i]=(rht[i+1]*bs%mod+t[i])%mod;
for(int i=1;i<=n;i++){
int l=1,r=min(i,n-i+1),res=1;
while(l<=r){
int mid=l+r>>1;
if((hs[i]-hs[i-mid]*pw[mid]%mod+mod)%mod==(rhs[i]-rhs[i+mid]*pw[mid]%mod+mod)%mod) res=mid,l=mid+1;
else r=mid-1;
}
l=0,r=min(i-res,n-(i+res-1)+1);
int res2=0;
while(l<=r){
int mid=l+r>>1;
if((hs[i-res]-hs[i-res-mid]*pw[mid]%mod+mod)%mod==(rht[i+res-1]-rht[i+res-1+mid]*pw[mid]%mod+mod)%mod) res2=mid,l=mid+1;
else r=mid-1;
}
cmax(ans,2*res-1+2*res2);
}
for(int i=1;i<n;i++){
int l=0,r=min(i,n-i),res=0;
while(l<=r){
int mid=l+r>>1;
if((hs[i]-hs[i-mid]*pw[mid]%mod+mod)%mod==(rhs[i+1]-rhs[i+mid+1]*pw[mid]%mod+mod)%mod) res=mid,l=mid+1;
else r=mid-1;
}
l=0,r=min(i-res,n-(i+res)+1);
int res2=0;
while(l<=r){
int mid=l+r>>1;
if((hs[i-res]-hs[i-res-mid]*pw[mid]%mod+mod)%mod==(rht[i+res]-rht[i+res+mid]*pw[mid]%mod+mod)%mod) res2=mid,l=mid+1;
else r=mid-1;
}
cmax(ans,2*res+2*res2);
}
for(int i=1;i<=n;i++){
int l=1,r=min(i,n-i+1),res=1;
while(l<=r){
int mid=l+r>>1;
if((ht[i]-ht[i-mid]*pw[mid]%mod+mod)%mod==(rht[i]-rht[i+mid]*pw[mid]%mod+mod)%mod) res=mid,l=mid+1;
else r=mid-1;
}
l=0,r=min(i-res+1,n-(i+res-1));
int res2=0;
while(l<=r){
int mid=l+r>>1;
if((hs[i-res+1]-hs[i-res+1-mid]*pw[mid]%mod+mod)%mod==(rht[i+res]-rht[i+res+mid]*pw[mid]%mod+mod)%mod) res2=mid,l=mid+1;
else r=mid-1;
}
cmax(ans,2*res-1+2*res2);
}
for(int i=1;i<n;i++){
int l=0,r=min(i,n-i),res=0;
while(l<=r){
int mid=l+r>>1;
if((ht[i]-ht[i-mid]*pw[mid]%mod+mod)%mod==(rht[i+1]-rht[i+1+mid]*pw[mid]%mod+mod)%mod) res=mid,l=mid+1;
else r=mid-1;
}
l=0,r=min(i-res+1,n-(i+res));
int res2=0;
while(l<=r){
int mid=l+r>>1;
if((hs[i-res+1]-hs[i-res+1-mid]*pw[mid]%mod+mod)%mod==(rht[i+res+1]-rht[i+res+mid+1]*pw[mid]%mod+mod)%mod) res2=mid,l=mid+1;
else r=mid-1;
}
cmax(ans,2*res+2*res2);
}
for(int i=1;i<=n;i++){
int l=1,r=min(i,n-i+1),res=0;
while(l<=r){
int mid=l+r>>1;
if((hs[i]-hs[i-mid]*pw[mid]%mod+mod)%mod==(rht[i]-rht[i+mid]*pw[mid]%mod+mod)%mod) res=mid,l=mid+1;
else r=mid-1;
}
cmax(ans,2*res);
}
cout<<ans<<endl;
return;
}
string RdFile="c";
bool en_memory;
signed main(){
auto bg_clock=chrono::high_resolution_clock::now();
#ifdef ONLINE_JUDGE
// freopen((RdFile+".in").c_str(),"r",stdin);
// freopen((RdFile+".out").c_str(),"w",stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// cin>>Case;
while(Case--) Main();
auto en_clock=chrono::high_resolution_clock::now();
auto duration_clock=chrono::duration_cast<chrono::microseconds>(en_clock-bg_clock);
#ifndef ONLINE_JUDGE
cerr<<endl<<"code_time_used: "<<duration_clock.count()*0.001<<"ms"<<endl;
cerr<<"code_memory_used: "<<(&en_memory-&bg_memory)/1024.0/1024<<"MB"<<endl;
#endif
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 30
Accepted
Test #1:
score: 30
Accepted
time: 0ms
memory: 3760kb
input:
1000 mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...
output:
6
result:
ok single line: '6'
Test #2:
score: 30
Accepted
time: 1ms
memory: 3772kb
input:
1000 wvitzoxwlmhexjuqvoxksetoupgkhattucdzfevqorkdlsymjuvhobdrjsodtipwpfhipsdnyvqtsbbasrrvyybijzmpwseckztnpnkqswgkaeivflhwevhxcchjsnelqcixexkntwiuolsditpdwypgerzijziyrgqkwuucnqaehuwkpyrmwewjitvsaebyytznbtnkulnepceeloyjpfhcdpqfqhvzsmkcynjwztmkbnqaxnikfuiutocahdfbvsgdskgwqmzizzjlbqxnngftdohetabpjzpqzyc...
output:
7
result:
ok single line: '7'
Test #3:
score: 30
Accepted
time: 1ms
memory: 3888kb
input:
1000 abababaabaababbbbabbbbabbbbbbabbbaabbbaababaabaabbabbbbaabbaabaaaabbaaabbbbaaaaaabbbbababaababbaabbbbbbbbabbaababbbbabbaabbbabaaababbaababbbaabaabaababaaababbaaaababbbbbaaabbaabbaaabbaaaaabaaaaaabbbbbaaabbbbbaabbbbababaabaabbbbaaaaababaaaababbbbbbaababbbaaaababaabaabaabaaaaaabbabbabbbbbbbbbbabb...
output:
28
result:
ok single line: '28'
Test #4:
score: 30
Accepted
time: 1ms
memory: 3988kb
input:
1000 ababbababababbaababaaabaabaababbaabbbabaababbaaababbabbbbaabbababbbababbabababbaabbbaababbabaaaaabbbbbaaaaaaaaabbbbaabbbaabbababaaabababbaaaabababbbaabaabbabbaabaaaaaaabaaabaaababaaaababbaaabaabbbbbbaabbabaaabaabbbbabbababbbaaaaabbabbaabbaabbaabaaabaaabbbbbaabaaaaaababbbbbabbbabbbabababbbbbabaa...
output:
27
result:
ok single line: '27'
Test #5:
score: 30
Accepted
time: 1ms
memory: 3820kb
input:
1000 abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabba...
output:
987
result:
ok single line: '987'
Test #6:
score: 30
Accepted
time: 1ms
memory: 3792kb
input:
1000 aaaaaaababbabbabaabaaaaababaaaaaabaabaaaabaaaaaaabbbabaabbaaabaaaaaaabaaaaaaaabaaabbaababaaaaaaaaabbaabbabbaaaaabaaaaaaaabbaaabaaaaaaaaaaabaabbbbbaaaabaaaaaaaaabbbaaaaabaaabaaaaaaaaaaaaaababaaaaabbaabbaaaabaabaaaababaaaaaababaaaaabaaaaaaabaaaababaaaabbaaaabaaaaabaaaaaaaabaaaaaaabaaaaaaaaaaaabaa...
output:
45
result:
ok single line: '45'
Test #7:
score: 30
Accepted
time: 1ms
memory: 3824kb
input:
1000 aaaaaabaaaaaaaababaaaaaaababaaaabaabaaaaabaabaaaabbaaaaabaababaaaaaaaaaaabaaaabaaaaaaaaaaaaaaaaaabbaaaaaaababaabaaaabababaaaaabbaaaaaabbababaaabbaaababbaaaabbababaaaaaaaaabbbaaaababaaaaabaaaabbaabaaaaaabbaabaaaaaaaaaaabaaaababbaaaaaaaababbabaaaaaaaaabaaaabaaaaabaaaaaaaaaaaabaaaabaaababaabaabaab...
output:
45
result:
ok single line: '45'
Test #8:
score: 30
Accepted
time: 1ms
memory: 3984kb
input:
1000 aabaaaabaaaabaaabaabbbaabaabbbaaaaaaaaaabaaaaabaababaabaabaaaaaaaaaabbabbaaaaaaaabaabbbbbaaaabbabbbaaaaaabababbaaaabaaaaaaaaabaaaaaaaabaaaaaabbaaaaabaaaaaababaaababaaaabaaaaaabaaaaaaabaaaaabbaaaaabaababaaaabbaaabbaabaabaaaaababbababaaabbbabaabaaabaaabaababbabaababaaaaabaaababaaaaaaaaaabbaaaabaa...
output:
36
result:
ok single line: '36'
Test #9:
score: 30
Accepted
time: 1ms
memory: 3984kb
input:
1000 aaaaaabaabaaaaaaabaaaaaabaabaaaaaaaaabaabaaaaaaababaaaaabaaabaabaaabaaaaaaaaaaaaabbbbbabaaaaaaabaaaaabaaabaaaaabababaaabaaabaabaabaaaabbaabaaaaaaaaaaaaaaabbaaaaabaabbabbbaaabbbabaababbaabaaaabbaaaabaabbbaaaaaaaaaabaabaaaabbaaaabbbbaaabaaaaabaaababaaaaaaaaaabbabbabaaaaaaaaaaaaaaaabaababbaaaababa...
output:
50
result:
ok single line: '50'
Test #10:
score: 30
Accepted
time: 1ms
memory: 3652kb
input:
1000 aaccbdbabdaaddabaabaaaacbbccdbabbaacabcdababdcacadababaadaaaadabacababcdbaabaaaabdbabbdcaacccaaacababaacbcacaaabbabbaaabcbaaabaababbaaacbaacaaacabdccbbbaabaccacadbbcaabacadaababbaaabababbacaabbaaabcdaabaaaaaabaababaabcabacaabacaaaaaacaaabcbcabcbbcbbbaacaadadbadbbadcabababcabbcbbdadbdababaaadcab...
output:
20
result:
ok single line: '20'
Subtask #2:
score: 20
Accepted
Test #11:
score: 20
Accepted
time: 63ms
memory: 7868kb
input:
100000 ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...
output:
9
result:
ok single line: '9'
Test #12:
score: 20
Accepted
time: 67ms
memory: 7708kb
input:
100000 fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...
output:
9
result:
ok single line: '9'
Test #13:
score: 20
Accepted
time: 68ms
memory: 7780kb
input:
99999 biwnbsgdlxognjnepijlgbfbbahicjfqhdhcielcovdflacbrgcfapifaylqfmvipcccoofthuutfheboncacenchdgfljpidjbasdsikduidkbdqckmlnbfaidlincqkccbbpmnqnpbjoclgeduitraqmdfgdqinhddgberlbnlgggoafgqllbifekoccpgemcgdiiackkcfjgddhieabhzdjfwegcbuncdadebglitgwcbpmclfijmqtbbnbbrcehhanjgbddiaoimmkehtloreemecckjejifck...
output:
11
result:
ok single line: '11'
Test #14:
score: 20
Accepted
time: 62ms
memory: 7732kb
input:
99999 chgjcjipccsmclcpjqmbrcpaqdggbdodxbcejbklpjhkefeidkjojjjbljhtykbcdgnnjeictgjgliegyfilmlkqkgddpefibjusamblbpqfbbvcfkgfagikbujlbjvenjbmcadceadnltdeksatckmkjkscojeqbpaaglggxhideqhkhibchdasadfggcoihhcwlphbeevohhohtthepedqfggbdglidnatocrkhnkijraddqbesaiajimdhdmvbgodlcglqqmkeehcfabeaatjdinzhijewfoxhh...
output:
9
result:
ok single line: '9'
Test #15:
score: 20
Accepted
time: 55ms
memory: 7676kb
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: 68ms
memory: 7732kb
input:
100000 vucutyzmjlnyadjbpqkrlqvzuponzxrvqsqqgbemhzjftdkksfgspeuonmjwlbirvszhcafcxpeubixvxetwyyqmftbobhodwaiwrcwdvddohalyqgaatvpflorvjypszbvzpwiaxxgievaozquixcndkxqfxcxaiygyqcgdebogwzquvqfljgjcvvhpirfzqlkwctibngdsffpormliyhrkcbxwxoaoovaawldfenziwnlahllzhjsvdhzekcqekayusmvzrgsdiiymjxfiddhawhgxathvnsedf...
output:
10
result:
ok single line: '10'
Test #17:
score: 50
Accepted
time: 67ms
memory: 7740kb
input:
100000 fotxrzsqxuaaiiqmiymhtfdipylgdmxizgzqrgbrmdemonbisusgbmmsgtyoaqgdmxwoxayxkszpvpypzjoapilopvhyiyhckcccaalqriunudgfifgvdiufjtukpsmdfjjzftszwizrwoxuqsujchtrywpiiineoscbvarbalizfyydbctxpuwndzgshavpygfcmxkorbcppbatauqqkumaqsjcupnihewaukjajqgdvatobxjgdcbevlxpkjdvpofwtctivkexpwnbwvwbhcmlivuvifpptiupy...
output:
9
result:
ok single line: '9'
Test #18:
score: 50
Accepted
time: 70ms
memory: 7992kb
input:
100000 baaabababbbaabbbbaabbabbababbbbbaaaaabaabbbbbbaaabaabaaabababbabbabbaababbaababbbabaaaaabbbabbabaaaabaabbbbababaaaaabbbbbabbbababbbbbaaabbaaabaabaaababbababbabaaaaaaaababaaabaababbbababbbbabbbabaaababbababbbababaabbaabbabaaaabaaabbbabbaabbabbbbbbabbbbaaaaaaaaaaabbbaabaaaabbbabbbaabababbbbaabb...
output:
40
result:
ok single line: '40'
Test #19:
score: 50
Accepted
time: 76ms
memory: 7684kb
input:
100000 babbbbaabaaaaaaaaaabbbbababababababababbabaaabbaaaaabaaaabaaaaababaabaabaabbbbabbbaabababbbaaabaaaaaaababaabababababbaabbbaabaabbbbbbbabaabbaabaaaababbbaabaaabaaaabbabbababbaabbabbbaabbbaababbaabaabaabbabbbabaaaaaaaaaabaabbabaaaaababaabbababbbabababbbbabbbbababababaabbabbababbaababababbbbaaba...
output:
43
result:
ok single line: '43'
Test #20:
score: 50
Accepted
time: 76ms
memory: 7964kb
input:
100000 aabaabbaaaaabbbbbaaaaaaaaaaaaaabbaaaaaaaaabaaaabbaaaaaabaaaaabaabbaaabababaaabbaaaaaaaaaabbabbbaaaaaaabaaabbbaabaaabaaabaaaaaaaaaabaabaaaababaaaaaabbaaaaaaababaabaaaaabababaaaaaaaaaababaaaababbaaabaaaabaaaaabaababbaaaaabbaaabaabaabaaaaababaaaaabbaaaabaaaaaaabaaaaaaaaabaabaaaaaabaababbbabaaaba...
output:
75
result:
ok single line: '75'
Test #21:
score: 50
Accepted
time: 77ms
memory: 7900kb
input:
100000 aaaabaabaaabaabbaaaabbbaaaaaaabaabaabaabaaaababaaaaabaaaaabbabaabbaabaaaaaabaaaaaaaaaaaaabaabbabaaaaaabaaaaaaaaaaaabaaaabbbabaaaaaabaaaababaaaabaaaaaabbaaaaaaaaabababaaaaabaabababaaabbababaaaaababababbaaaaaabaabaaaabbababbbaaabaaaabaabaaaaabaabaaaaaabbbaaaaaaabababababbaaabaaabaaababaaaabaaaa...
output:
58
result:
ok single line: '58'
Test #22:
score: 50
Accepted
time: 75ms
memory: 7996kb
input:
100000 abbaaaaaaabaaaaaaaabaaaaaaaaaaaaaaaaabbabaaabaaaaaaaaaaaaaaabaaabbbaabaaaaabaaaaaaabaaaaabaabaabaaaababaaaaaaaaaaaaaaaaabaaabbabaaaaaaabaaaaaaabaaaaaabaaaaabaaabbaaaabbaabbaaababaababaaaaaabaaaaabaaaaaaaaaaaaababaaaaabaaaaaabbbabaaaaaaaaaaaaabaaaaaaaabbbaabaaabaaabaaabbabaabaaabbabaaaaaaaabba...
output:
67
result:
ok single line: '67'
Test #23:
score: 50
Accepted
time: 75ms
memory: 7676kb
input:
100000 bbaaaaabaaaaaaaaaabbaabaaaaaaabbbaabababaaababbaaaabaaaaaaaaaabaaaabbaaaaabaaaaaabbaabbbbaaabbaaaaaabbabaaabaababbaababaaabaaaaaaaaaabaaaaabbaaaaabbaaaabaaabababbbaabaaaaabaabaaaaaaabaaaaaaabaabababbbaaaaaaaaaaaaaaaaabaaaaaaabaaaaaababbbababaabaaabbbaaaaabaaaaaaabaabababaaaaaabaaaabbaabababaa...
output:
55
result:
ok single line: '55'
Test #24:
score: 50
Accepted
time: 67ms
memory: 7672kb
input:
100000 cabcacbbacbbaacbaabbaabbaabacdcadbbccabbccbbaabacacbabaccbaabbbaaabaddbcaccdcaababaaabbbbbcdacaabababcbbcbcabbbdbbbcadaadabcabbacabbdbbcaaabacaabbabbabacbabbabaadabbabdbabcbdcaacaddbbbabdabaaabcabcababbcbbaaccabbbbacaabbacdaaaabaaaaccaaabaaccbaccbbababdacaacabcaaabbaaacbcbaaabcaaabcaabbabbcad...
output:
25
result:
ok single line: '25'
Test #25:
score: 50
Accepted
time: 68ms
memory: 7796kb
input:
100000 abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbab...
output:
96421
result:
ok single line: '96421'
Test #26:
score: 50
Accepted
time: 0ms
memory: 3752kb
input:
5 pkusc pkukp
output:
6
result:
ok single line: '6'