QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#558079#8668. 回文路径byron100000 0ms0kbC++142.1kb2024-09-11 14:03:412024-09-11 14:03:42

Judging History

你现在查看的是最新测评结果

  • [2024-09-11 14:03:42]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-09-11 14:03:41]
  • 提交

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%