Submission #138342

#	Time	Username	Problem	Language	Result	Execution time	Memory
138342		mehrdad_sohrabi	Palinilap (COI16_palinilap)	C++14	100 / 100	483 ms	33812 KiB

palinilap

#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < int, int >
#define F first
#define S second
#define int long long int
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize ("Ofast")
using namespace std;
/// khodaya komak kon
/// ya navid navid
/// ye tec khaphan ke yadam bemone : age jayi didi soale masir hamiltoni mikhad rasasho bokon yal oilery;https://mobomovie1.top/series/%D8%AF%D8%A7%D9%86%D9%84%D9%88%D8%AF-%D8%B3%D8%B1%DB%8C%D8%A7%D9%84-%D9%81%D8%B1%DB%8C%D9%86%D8%AC-fringe-2008-2013-%D8%A8%D8%A7-%D8%B2%D9%8A%D8%B1%D9%86%D9%88%D9%8A%D8%B3-%D9%81%D8%A7%D8%B1/
/// age ye ja mikhasti to dp az ozv i k ta entekhab koni bejash ye log bezan (nominal) hamoon 2**k va o 1 ent kon

const int N=1e5+100;
ll ph1[N];
ll ph2[N];
ll mod=1e9+7;
ll p[N];
ll a[N];
ll n;
ll inv[N];
char c[N];
ll b[N];
ll power(ll n,ll k){
    if (k==0){
        return 1;
    }
    if (k%2==1){
        ll x=power(n,k/2);
        return x*x%mod*n%mod;
    }
    ll x=power(n,k/2);
    return x*x%mod;
}
ll h1(ll l,ll r){
    ll z=ph1[r-1];
    z-=ph1[l-1];
    z+=mod;
    z%=mod;
    z*=inv[l-1];
    z%=mod;
    return z;
}
ll h2(ll l,ll r){
    ll z=ph2[l];
    z-=ph2[r];
    z+=mod;
    z%=mod;
    z*=inv[n-r+1];
    z%=mod;
    return z;
}
ll bs(ll s,ll f){
    ll l=0,r=min(s,n-f)+1;
    while(r-l>1){
        ll mid=(r+l)/2;
        ll z=h1(s-mid+1,s+1);
        ll w=h2(f+1,f+mid+1);

        if (z==w){
            l=mid;
        }
        else{
            r=mid;
        }
    }
    return l;
}
ll ans[N][30];
ll g[N];
ll baze1[N],baze2[N];
ll baze3[N],baze4[N],baze5[N],baze6[N];
int32_t main(){

    p[0]=1;
    inv[0]=1;
    for (int i=1;i<N;i++){
        p[i]=p[i-1]*311%mod;
        inv[i]=power(p[i],mod-2);
    }
    string we;
    cin >> we;
    n=we.size();
    for (int i=0;i<n;i++){
        c[i]=we[i];
        a[i]=c[i]-'a'+1;
    }
    for (int i=1;i<=n;i++){
        ph1[i]=ph1[i-1]%mod+a[i-1]*p[i-1]%mod;
        ph1[i]%=mod;
    }
    for (int i=n;i>0;i--){
        ph2[i]=ph2[i+1]+a[i-1]*p[n-i]%mod;
        ph2[i]%=mod;
    }
    ll u=1;
    for (int i=1;i<n;i++){
        ll d=bs(i,i);
        baze1[i]+=d;
        baze5[i-d]++;
        baze3[i]++;
    //cout << d << endl;
       // baze1.pb({i-d,i});
        baze2[i]+=d;
        baze6[i]++;
        baze4[i+d]+=1;
       // baze2.pb({i,i+d});
       u+=d;
        if (i-d>0 && i+d<=n-1){
            ll w=bs(i-d-1,i+d+1);
            ans[i-d-1][a[i+d]]+=w+1;
            ans[i+d][a[i-d-1]]+=w+1;
          //  cout << i << " " << w << " " << a[i-d-1] << " " << a[i+d] << " " << d << endl;
        }

        d=bs(i,i+1);
        u+=d+1;
        baze1[i]+=d;
        baze5[i-d]++;
        baze3[i]+=1;
        baze2[i+1]+=d;
        baze4[i+d+1]++;
        baze6[i+1]++;
        //baze1.pb({i-d,i});
      //  baze2.pb({i+1,i+d+1});
     //   cout << i << " " << d << endl;
        if (i-d>0 && i+1+d<=n-1){
            ll w=bs(i-d-1,i+1+d+1);
            ans[i-d-1][a[i+d+1]]+=w+1;
            ans[i+d+1][a[i-d-1]]+=w+1;
          //  cout << i << " : " << w << " " << a[i-d-1] << " " << a[i+d+1] << endl;
        }
    }

    ll cnt1=0,cnt2=0;
    ll b1=0,b2=0;
    ll sum=0;
    for (int i=0;i<n;i++){
        b1-=baze3[i];
       // b2-=baze4[i];
        sum-=baze1[i];
        b1+=baze5[i];
        sum+=b1;
        sum-=b2;
        b2+=baze6[i];
        sum+=baze2[i];
        b2-=baze4[i];
        g[i]=sum;
        //cout << i << " " << sum << " " << ans[i][1] << endl;
    }
    ll ma=0;
    for (int i=0;i<n;i++){
        for (int j=0;j<29;j++){
            ma=max(ma,ans[i][j]-g[i]);
           // cout << i << " df " << j << " " << ans[i][j] << " " << g[i] << endl;
        }

    }
    cout << u+ma << endl;

}

Compilation message (stderr)

palinilap.cpp: In function 'int32_t main()':
palinilap.cpp:138:8: warning: unused variable 'cnt1' [-Wunused-variable]
     ll cnt1=0,cnt2=0;
        ^~~~
palinilap.cpp:138:15: warning: unused variable 'cnt2' [-Wunused-variable]
     ll cnt1=0,cnt2=0;
               ^~~~

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