Submission #955184

#	Time	Username	Problem	Language	Result	Execution time	Memory
955184		jhinezeal123	Palinilap (COI16_palinilap)	C++17	37 / 100	140 ms	94452 KiB

palinilap

#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define iii pair<int,ii>
#define vii vector<ii>
#define fi first
#define se second
#define endl '\n'
#define show(T) {for (auto x:T) cout<<x<<' ';cout<<endl;}
using namespace std;
const double eps = 0.0000001;
const int mod1 = 998244353,mod2 = 1e9+7;
const int N = 500005;
const int MATRIX_SIZE = 64;
int n,ans,ansT,them[N][30],base1=31,base2=575,sum1,sum2,sl1,sl2;
ii Hash1[N],Hash2[N],P[N];
vector <int> add1[N],sub1[N],add2[N],sub2[N];
string s;
ii get1(int l,int r){
    return {(Hash1[r].fi-Hash1[l-1].fi*P[r-l+1].fi+mod1*mod1)%mod1,(Hash1[r].se-Hash1[l-1].se*P[r-l+1].se+mod2*mod2)%mod2};
}
ii get2(int l,int r){
    return {(Hash2[l].fi-Hash2[r+1].fi*P[r-l+1].fi+mod1*mod1)%mod1,(Hash2[l].se-Hash2[r+1].se*P[r-l+1].se+mod2*mod2)%mod2};
}
void even(int pos){
    int res=0,l=1,r=min(pos,n-pos);
    while (l<=r){
        int mid=(l+r)>>1;
        if (get1(pos-mid+1,pos)==get2(pos+1,pos+mid)){
            res=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    // cout<<pos<<" 1 "<<res<<endl;
    add2[pos-res+1].push_back(pos-res+1);
    sub2[pos+1].push_back(pos-res+1);
    add1[pos+1].push_back(pos+res);
    sub1[pos+res+1].push_back(pos+res);
    ansT+=res;
    if (res==min(pos,n-pos)) return;
    int tam=res+1;
    l=res+2;
    r=min(pos,n-pos);
    while (l<=r){
        int mid=(l+r)>>1;
        if (get1(pos-mid+1,pos-res-1)==get2(pos+res+2,pos+mid)){
            tam=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    // cout<<pos<<" 1 "<<tam<<endl;
    // cout<<pos-res<<' '<<s[pos+res+1]-'a'+1<<' '<<pos+res+1<<' '<<s[pos-res]-'a'+1<<endl;
    tam-=res;
    them[pos-res][s[pos+res+1]-'a'+1]+=tam;
    them[pos+res+1][s[pos-res]-'a'+1]+=tam;
}
void odd(int pos){
    int res=0,l=1,r=min(pos-1,n-pos);
    while (l<=r){
        int mid=(l+r)>>1;
        if (get1(pos-mid,pos-1)==get2(pos+1,pos+mid)){
            res=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    // cout<<pos<<" 2 "<<res<<endl;
    ansT+=res+1;
    add2[pos-res].push_back(pos-res);
    sub2[pos-res].push_back(pos-res);
    add1[pos+1].push_back(pos+res);
    sub1[pos+res+1].push_back(pos+res);
    if (res==min(pos-1,n-pos)) return;
    int tam=res+1;
    l=res+2;
    r=min(pos-1,n-pos);
    while (l<=r){
        int mid=(l+r)>>1;
        if (get1(pos-mid,pos-res-2)==get2(pos+res+2,pos+mid)){
            tam=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    // cout<<pos<<" 2 "<<tam<<endl;
    // cout<<pos-res-1<<' '<<s[pos+res+1]-'a'+1<<' '<<pos+res+1<<' '<<s[pos-res-1]-'a'+1<<endl;
    tam-=res;
    them[pos-res-1][s[pos+res+1]-'a'+1]+=tam;
    them[pos+res+1][s[pos-res-1]-'a'+1]+=tam;
}
void FindPalind(){
    for (int i=1;i<=n;++i){
        even(i);
        odd(i);
    }
}
void Dp(){
    for (int i=1,tru,cong;i<=n;++i){
        for (auto it:add1[i]){
            ++sl1;
            sum1+=it;
        }
        for (auto it:add2[i]){
            ++sl2;
            sum2+=it;
        }
        for (auto it:sub1[i]){
            --sl1;
            sum1-=it;
        }
        for (auto it:sub2[i]){
            --sl2;
            sum2-=it;
        }
        tru=sum1-sl1*(i-1)+sl2*(i+1)-sum2;
        for (int j=1;j<=26;++j){
            cong=them[i][j];
            ans=max(ans,ansT-tru+cong);
        }
    }
}
void solve(){
    cin>>s;
    n=s.size();
    s=' '+s+'$';
    P[0]={1,1};
    for (int i=1;i<=n;++i){
        P[i]={P[i-1].fi*base1%mod1,P[i-1].se*base2%mod2};
        Hash1[i]={(Hash1[i-1].fi*base1+s[i]-'a'+1)%mod1,(Hash1[i-1].se*base2+s[i]-'a'+1)%mod2};
    }
    for (int i=n;i>=1;--i){
        Hash2[i]={(Hash2[i+1].fi*base1+s[i]-'a'+1)%mod1,(Hash2[i+1].se*base2+s[i]-'a'+1)%mod2};
    }
    FindPalind();
    ans=ansT;
    Dp();
    cout<<ans;
}
main() {
   
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // init();
    solve();
    // cout<<clock()/1000.0;
}

Compilation message (stderr)

palinilap.cpp:141:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  141 | main() {
      | ^~~~

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