Submission #989179

#	Time	Username	Problem	Language	Result	Execution time	Memory
989179		0pt1mus23	Palinilap (COI16_palinilap)	C++14	0 / 100	1098 ms	12632 KiB

palinilap

/*
! Bismillahirrahmanirrahim
*/
#pragma GCC optimize("O3", "inline")
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define ins insert
#define pb push_back
#define int long long int
#define pii pair<int, int>
#define str string
#define endl '\n'
#define drop(x) cout<<(x)<<endl;return;
/*
    m : 11059739 -> l ~23
    p : 4567896467
*/
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 1e9 + 7, sze = 1e6 + 50, inf = LLONG_MAX, prime = 17;

//\\
!!! dp ?recrusive? / binary search / greedy / sprase table / segment tree 
//
int poly[sze];
int p[sze];
int n;

int qry2(int l,int r,int lx,int rx){
    lx=n + (n - lx -1);
    rx=n + (n - rx -1);
    swap(lx,rx);
    // cout<<l<<" "<<r<<" "<<lx<<" "<<rx<<endl;
    if(min({l,r,lx,rx})<0 || max({l,r,lx,rx})>n*2-1){
        // cout<<l<<" "<<r<<" "<<lx<<" "<<rx<<endl;
        return 0;
    }
    int a = ( p[lx]  * 1LL * ( (poly[r+1] - poly[l]) % mod) + mod ) % mod;
    int b =  ( p[l]  * 1LL * ( (poly[rx+1] - poly[lx]) % mod) + mod ) % mod;
    return (a==b);
}
int ps(str s){
    memset(poly,0,sizeof poly);
    str t=s;
    reverse(all(t));
    s+=t; // lmao
    for(int i=1;i<=n+n;i++){
        poly[i] = ( poly[i-1] + ((s[i-1]-'a'+1)* 1LL * p[i]) % mod + mod)%mod;
    }
    // cout<<s<<endl;
    /*
        ab ba
        01 23
    */
    // cout<<qry(1,1,6,6)<<endl;
    // cout<<qry2(0,1,3,4)<<endl;

    int ans =n;
    // odd
    for(int i=0;i<n;i++){
        if(i>0){
            int l =0;
            int r = min((n-i -1),i) ;
            int mid = 0;

            while(l<=r){
                int m = (l+r)/2;
                // cout<<i<<" => "<<m<<" :: "<<i-m<<" "<<i-1<<" - "<<i+1<<" "<<i+m<<endl;
                
                if(qry2(i-m,i-1, i+1,i+m)){
                    l=m+1;
                    mid=m;
                }
                else{
                    r=m-1;
                }
            }
            ans+=mid;

            // cout<<i<<" odd "<<mid<<endl;
        }
        if(i+1<n){

            if(s[i]==s[i+1]){
                int mid=0;
                int l =0;
                int r = min(i, n - (i+1) -1 );
                while(l<=r){
                    int m = (l+r)/2;
                    // cout<<m<<" :: "<<i-m<<" "<<i<<" - "<<i+1<<" "<<i+1+m<<endl;
                    if(qry2(i-m,i,i+1,i+1+m)){
                        mid=m;
                        l=m+1;
                    }
                    else{
                        r=m-1;
                    }
                }
                // cout<<i<<" even "<<mid<<endl;
                ans+=mid+1;
            }
        }
    }


    return ans;

}

void gkd(){
    str s;
    cin>>s;
    n=(s.size());
    
    p[0]=1;
    for(int i=1;i<=n*2;i++){
        p[i]=(p[i-1]*prime )%mod;
    }
    // cout<<qry(1,1,6,6)<<endl;
    int mx =0;
    // drop(ps(s));
    for(int i=0;i<n;i++){
        char ch=s[i];
        for(int j=0;j<26;j++){
            s[i]=char('a'+j);
            
            mx=max(mx,ps(s));

            // cout<<s<<" "<<mx<<endl;
        }
        s[i]=ch;
    }
    drop(mx);
}


signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int tt = 1;
    // cin>>tt;
    while (tt--)gkd();
}

Compilation message (stderr)

palinilap.cpp:22:1: warning: multi-line comment [-Wcomment]
   22 | //\\
      | ^

• Subtask 1: 0 / 17
• Subtask 2: 0 / 37
• Subtask 3: 0 / 46