QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#558079 | #8668. 回文路径 | byron10000 | 0 | 0ms | 0kb | C++14 | 2.1kb | 2024-09-11 14:03:41 | 2024-09-11 14:03:42 |
answer
#if defined(_USE_PCH_)
#include "pch.hpp"
#else
#include <bits/stdc++.h>
#endif
#define RNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_<=V_##_END; V_++)
#define IRNG(V_, A_, B_) for(int V_=(A_), V_##_END=(B_); V_>=V_##_END; V_--)
#ifdef _WIN32
#define long __int64
#endif
using namespace std;
const int MAXN=1e5+10, BASE[] {29,37},MOD[] {998244353,1000000007};
int n;
char S[2][MAXN];
array<long,2> hash_[4][MAXN],pw[MAXN];
array<long,2> slice_(int k,int l,int r){
assert(1<=l&&l<=r&&r<=n);
array<long,2> ret;
RNG(t,0,1) ret[t]=(hash_[k][r][t]-hash_[k][l-1][t]*pw[r-l+1][t]%MOD[t]+MOD[t])%MOD[t];
return ret;
}
int find(int k1,int r1,int k2,int l2){
int l=1,r=min(n-l2+1,r1),ret=0;
while(l<=r){
int mid=(l+r)/2;
if(slice_(k1*2+1,n-(r1)+1,n-(r1-mid+1)+1)==slice_(k2*2,l2,l2+mid-1)) ret=mid,l=mid+1;
else r=mid-1;
}
return ret;
}
int solve(){
RNG(t,0,1){
pw[0][t]=1;
RNG(i,1,n) pw[i][t]=pw[i-1][t]*BASE[t]%MOD[t];
}
RNG(k,0,1){
RNG(i,1,n){
RNG(t,0,1) hash_[k*2][i][t]=(hash_[k*2][i-1][t]*BASE[t]+(S[k][i]-'a'+1))%MOD[t];
}
RNG(i,1,n){
RNG(t,0,1) hash_[k*2+1][i][t]=(hash_[k*2+1][i-1][t]*BASE[t]+(S[k][n-i+1]-'a'+1))%MOD[t];
}
}
int ans=0;
RNG(i,1,n){
{ // odd
int x=find(0,i-1,0,i+1);
int y=find(0,i-x-1,1,i+x);
ans=max(ans,x*2+y*2+1);
}
if(i!=n) { // even
int x=find(0,i,0,i+1);
int y=find(0,i-x,1,i+x);
ans=max(ans,x*2+y*2);
}
}
return ans;
}
int main(){
#if defined(_LOCAL_)
freopen("in","r",stdin);
// freopen("out","w",stdout);
#else
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
#endif
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>(S[0]+1)>>(S[1]+1);
int ans=solve();
swap(S[0],S[1]),reverse(S[0]+1,S[0]+n+1),reverse(S[1]+1,S[1]+n+1);
ans=max(ans,solve());
cout<<ans<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Dangerous Syscalls
Test #1:
score: 0
Dangerous Syscalls
input:
1000 mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...
output:
result:
Subtask #2:
score: 0
Dangerous Syscalls
Test #11:
score: 0
Dangerous Syscalls
input:
100000 ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #1:
0%