QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#561324 | #8668. 回文路径 | hhiron | 0 | 43ms | 11284kb | C++14 | 1.3kb | 2024-09-12 21:49:31 | 2024-09-12 21:49:32 |
Judging History
answer
#include<bits/stdc++.h>
#define INF 0x7fffffff
#define int long long
typedef long long ll;
using namespace std;
const int MOD=998244353;
const int N=5e5+5;
int n,l,r,len[N],po[N];
int has1l[N],has1r[N],has2l[N],has2r[N];
string s1,s2;
int gethash(int x,int y,int *a){
return (a[y]-a[x]*po[abs(y-x)]%MOD+MOD)%MOD;
}
int ans=0;
void solve(){
for(int i=1;i<=n;i++) has1l[i]=(has1l[i-1]*31%MOD+s1[i]-'a')%MOD;
for(int i=1;i<=n;i++) has2l[i]=(has2l[i-1]*31%MOD+s2[i]-'a')%MOD;
for(int i=n;i>=1;i--) has1r[i]=(has1r[i+1]*31%MOD+s1[i]-'a')%MOD;
for(int i=n;i>=1;i--) has2r[i]=(has2l[i+1]*31%MOD+s2[i]-'a')%MOD;
// cout<<s1<<endl;
for(int i=1;i<=n;i++){
int l=-1,r=min(n-i,i-1);
while(r-l>1){
int mid=(l+r)>>1;
if(gethash(i-mid,i+mid,has1l)==gethash(i+mid,i-mid,has1r)) l=mid;
else r=mid;
}int poil=i-r-1,poir=i+r;
ans=max(ans,r*2+1);
l=0,r=min(poil-1,n-poir);
if(s1[poil]!=s2[poir]) continue;
// while(r-l>1){
// int mid=(l+r)>>1;
// if(gethash(mid))
// }
}
}
signed main(){
cin>>n>>s1>>s2;
s1=" "+s1; s2=" "+s2;
po[0]=1;
for(int i=1;i<=n;i++) po[i]=po[i-1]*31%MOD;
solve();
swap(s1,s2);
for(int i=1;i<=n/2;i++) swap(s1[i],s1[n-i+1]);
for(int i=1;i<=n/2;i++) swap(s2[i],s2[n-i+1]);
solve();
printf("%lld",ans);
return 0;
}
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: 5780kb
input:
1000 mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...
output:
7
result:
wrong answer 1st lines differ - expected: '6', found: '7'
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 43ms
memory: 11284kb
input:
100000 ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...
output:
11
result:
wrong answer 1st lines differ - expected: '9', found: '11'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%