Submission #1150414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150414		nrg_studio	Palinilap (COI16_palinilap)	C++20	100 / 100	95 ms	31044 KiB

palinilap

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define v vector

using T = __int128;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
ll mod = (1LL<<61)-1, b = uniform_int_distribution<ll>(0, 10000)(rng);
ll mul(ll a, ll b) {return (__int128)a*b%mod;}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    string s; cin >> s;
    int n = s.size();
    s = '0'+s;

    v<T> fac(n+1,0), hsh(n+1,0), hsh2(n+2,0);
    fac[0] = 1;
    for (int i=0;i<n;i++) {
        fac[i+1] = fac[i]*b%mod;
        hsh[i+1] = ((fac[i]*(s[i+1]-'a'+1)%mod)+hsh[i])%mod;
        hsh2[n-i] = ((fac[i]*(s[n-i]-'a'+1)%mod)+hsh2[n-i+1])%mod;
    }
    auto check = [&](int l1, int r1, int l2, int r2) { // compare strings [l1,r1], [r2,l2]
        int p1 = l1, p2 = n-l2+1;
        T h1 = (hsh[r1]-hsh[l1-1]+mod)%mod, h2 = (hsh2[r2]-hsh2[l2+1]+mod)%mod;

        //cout<<(ll)h1<<' '<<(ll)h2<<'\n';

        if (p1<p2) {h1 = mul(h1,fac[p2-p1]);}
        else {h2 = mul(h2,fac[p1-p2]);}

        return (h1==h2);
    };
    
    v<v<ll>> change(n+1,v<ll>(26,0));
    v<ll> ps(n+3,0), pal(n+1);
    ll tot = 0;

    //cout <<check(1,6,7,12)<<'\n';
    //cout<<check(n-1,n,3,2) << '\n';
    //cout<<check(3,4,2,1)<<'\n';
    //cout<<hsh[2]<<' ' <<

    auto calc = [&](int i1, int i2, int doit) {
        int l = 0, h = min(i1-1,n-i2), m = (l+h)/2, ans;
        while (l <= h) {
            if (check(i2+1,i2+m,i1-1,i1-m)) {
                l = m+1;
                ans = m;
            } else {h = m-1;}
            m = (l+h)/2;
        }

        if (doit) {return ans;}
        
        // update prefix sum
        if (i1==i2) {pal[i1] += ans+1;}
        ps[i1-ans]++;
        ps[i1+1]--;
        ps[i2+1]--;
        ps[i2+ans+2]++;
        tot += ans+1;
        //cout<<i1<<' '<<i2<<' '<<ans+1<<'\n';

        if (ans!=min(i1-1,n-i2)) {
            l = ans+2, h = min(i1-1,n-i2), m = (l+h)/2; int ans2 = 0;
            while (l <= h) {
                if (check(i2+ans+2,i2+m,i1-ans-2,i1-m)) {
                    l = m+1;
                    ans2 = m-(ans+1);
                } else {h = m-1;}
                m = (l+h)/2;
            }
            change[i1-ans-1][s[i2+ans+1]-'a'] += ans2+1;
            change[i2+ans+1][s[i1-ans-1]-'a'] += ans2+1;
        }
        return 0;
    };
    for (int i=1;i<=n;i++) {
        calc(i,i,0);
        
        if (i<n) {
            if (s[i]==s[i+1]) {calc(i,i+1,0);}
            else {
                int z = calc(i,i+1,1)+1;
                change[i][s[i+1]-'a'] += z;
                change[i+1][s[i]-'a'] += z;
            }
        }
    }
    //return 0;
    ll ans = tot;
    for (int i=1;i<=n;i++) {
        ps[i+1] += ps[i];
    }
    for (int i=1;i<=n;i++) {
        ps[i+1] += ps[i];
        ps[i] -= pal[i];
        ll add = 0;
        for (int j=0;j<26;j++) {add = max(add,change[i][j]);}
        ans = max(ans,tot-ps[i]+add);
    }
    cout << ans << '\n';

    // run prefix sum
    // calculate answer

    
    /*
    calc number palindromes total!
    find number centered at each character with bin search/string hashing

    next, find num palindromes going through an index such that the index
    is not the center (because then, modifying that index will 100% delete
    all these palindromes)
    do this with double prefix sum

    next, we need to calculate number palindromes gained by changing an index
    to a character

    we basically calc palindromes but 1 mismatch allowed, so when calc
    total from each center, find the first mismatch, rectify it, then continue
    further, and store for those mismatched indices how many palindromes can
    be gained if we change to the other letter
    
    and so, go through each index/letter combo and subtract/add accordingly
    */
}

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