QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#558008 | #8668. 回文路径 | zero-range | 0 | 28ms | 9848kb | C++20 | 1.6kb | 2024-09-11 13:27:55 | 2024-09-11 13:27:56 |
Judging History
answer
#include<stdio.h>
#include<algorithm>
#define M 200005
using namespace std;
typedef unsigned long long ull;
constexpr ull bs=1000;
ull Ha[M],Hb[M],Pa[M],Pb[M],pw[M];
inline ull queh(ull *H,int l,int r){return H[r]-H[l-1]*pw[r-l+1];}
inline ull quep(ull *P,int l,int r){return P[l]-P[r+1]*pw[r-l+1];}
int n,res;
char a[M],b[M];
int main(){
pw[0]=1;
for(int i=1;i<M;++i) pw[i]=pw[i-1]*bs;
scanf("%d%s%s",&n,a+1,b+1);
for(int i=n;i;--i) a[i*2]=a[i],a[i*2+1]='#';
a[1]='#';
for(int i=n;i;--i) b[i*2+1]=b[i],b[i*2+2]='#';
b[1]='@',b[2]='#',a[n=n*2+2]='.';
for(int i=1;i<=n;++i) Ha[i]=Ha[i-1]*bs+a[i];
for(int i=n;i;--i) Pa[i]=Pa[i+1]*bs+a[i];
for(int i=1;i<=n;++i) Hb[i]=Hb[i-1]*bs+b[i];
for(int i=n;i;--i) Pb[i]=Pb[i+1]*bs+b[i];
for(int i=1;i<=n;++i){
int l=1,r=min(i-1,n-i),mid,ans=0;
while(l<=r){
mid=l+r>>1;
if(queh(Ha,i-mid,i-1)==quep(Pa,i+1,i+mid)) l=mid+1,ans=mid;
else r=mid-1;
}
int t=ans;
res=max(res,t*2+1);
l=1,r=min(i-t-1,n-i+1-t),ans=0;
while(l<=r){
mid=l+r>>1;
if(queh(Ha,i-t-mid,i-t-1)==quep(Pb,i+t,i+t+mid-1)) l=mid+1,ans=mid;
else r=mid-1;
}
res=max(res,(t+ans)*2+1);
}
for(int i=1;i<=n;++i){
int l=1,r=min(i-1,n-i),mid,ans=0;
while(l<=r){
mid=l+r>>1;
if(queh(Hb,i-mid,i-1)==quep(Pb,i+1,i+mid)) l=mid+1,ans=mid;
else r=mid-1;
}
int t=ans;
res=max(res,t*2+1);
l=1,r=min(i-t,n-i-t),ans=0;
while(l<=r){
mid=l+r>>1;
if(queh(Ha,i-t-mid+1,i-t)==quep(Pb,i+t+1,i+t+mid)) l=mid+1,ans=mid;
else r=mid-1;
}
res=max(res,(t+ans)*2+1);
}
printf("%d",res/2);
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 30
Accepted
time: 1ms
memory: 3700kb
input:
1000 mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...
output:
6
result:
ok single line: '6'
Test #2:
score: 30
Accepted
time: 1ms
memory: 4016kb
input:
1000 wvitzoxwlmhexjuqvoxksetoupgkhattucdzfevqorkdlsymjuvhobdrjsodtipwpfhipsdnyvqtsbbasrrvyybijzmpwseckztnpnkqswgkaeivflhwevhxcchjsnelqcixexkntwiuolsditpdwypgerzijziyrgqkwuucnqaehuwkpyrmwewjitvsaebyytznbtnkulnepceeloyjpfhcdpqfqhvzsmkcynjwztmkbnqaxnikfuiutocahdfbvsgdskgwqmzizzjlbqxnngftdohetabpjzpqzyc...
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Wrong Answer
time: 1ms
memory: 4484kb
input:
1000 abababaabaababbbbabbbbabbbbbbabbbaabbbaababaabaabbabbbbaabbaabaaaabbaaabbbbaaaaaabbbbababaababbaabbbbbbbbabbaababbbbabbaabbbabaaababbaababbbaabaabaababaaababbaaaababbbbbaaabbaabbaaabbaaaaabaaaaaabbbbbaaabbbbbaabbbbababaabaabbbbaaaaababaaaababbbbbbaababbbaaaababaabaabaabaaaaaabbabbabbbbbbbbbbabb...
output:
831
result:
wrong answer 1st lines differ - expected: '28', found: '831'
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 20
Accepted
time: 23ms
memory: 9840kb
input:
100000 ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...
output:
9
result:
ok single line: '9'
Test #12:
score: 20
Accepted
time: 27ms
memory: 9828kb
input:
100000 fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...
output:
9
result:
ok single line: '9'
Test #13:
score: 20
Accepted
time: 28ms
memory: 9788kb
input:
99999 biwnbsgdlxognjnepijlgbfbbahicjfqhdhcielcovdflacbrgcfapifaylqfmvipcccoofthuutfheboncacenchdgfljpidjbasdsikduidkbdqckmlnbfaidlincqkccbbpmnqnpbjoclgeduitraqmdfgdqinhddgberlbnlgggoafgqllbifekoccpgemcgdiiackkcfjgddhieabhzdjfwegcbuncdadebglitgwcbpmclfijmqtbbnbbrcehhanjgbddiaoimmkehtloreemecckjejifck...
output:
11
result:
ok single line: '11'
Test #14:
score: 20
Accepted
time: 24ms
memory: 9848kb
input:
99999 chgjcjipccsmclcpjqmbrcpaqdggbdodxbcejbklpjhkefeidkjojjjbljhtykbcdgnnjeictgjgliegyfilmlkqkgddpefibjusamblbpqfbbvcfkgfagikbujlbjvenjbmcadceadnltdeksatckmkjkscojeqbpaaglggxhideqhkhibchdasadfggcoihhcwlphbeevohhohtthepedqfggbdglidnatocrkhnkijraddqbesaiajimdhdmvbgodlcglqqmkeehcfabeaatjdinzhijewfoxhh...
output:
9
result:
ok single line: '9'
Test #15:
score: 0
Wrong Answer
time: 18ms
memory: 9780kb
input:
99999 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
100000
result:
wrong answer 1st lines differ - expected: '99999', found: '100000'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%