QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#557983 | #8668. 回文路径 | zero-range | 0 | 27ms | 9784kb | C++20 | 1.6kb | 2024-09-11 13:13:30 | 2024-09-11 13:13:31 |
Judging History
answer
#include<stdio.h>
#include<algorithm>
#define M 200005
using namespace std;
typedef unsigned long long ull;
constexpr ull bs=1e9+7;
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=2;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]='#';
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: 0
Wrong Answer
time: 1ms
memory: 4112kb
input:
1000 mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...
output:
0
result:
wrong answer 1st lines differ - expected: '6', found: '0'
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 27ms
memory: 9784kb
input:
100000 ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...
output:
0
result:
wrong answer 1st lines differ - expected: '9', found: '0'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%