Submission #418659

#	Time	Username	Problem	Language	Result	Execution time	Memory
418659		SirCovidThe19th	Palinilap (COI16_palinilap)	C++14	100 / 100	213 ms	27304 KiB

palinilap

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

#define ll long long
#define f first
#define s second

const int mx = 1e5+5, p = 5281, m1 = 1e9+7, m2 = 1e9+9;

int n; string str; 
pair<ll, ll> pPow[mx], hsh[2][mx]; 
ll create[mx][26]; pair<ll, ll> destroy[mx]; ll ans;

pair<ll, ll> getHash(int l, int g, int rev){ //hsh is 1 indexed, paraters are 0 indexed
    l++; g++; int dir[2] = {-1, 1}; if (rev == 1) swap(l, g); l += dir[rev];
    return {((hsh[rev][g].f-(hsh[rev][l].f*pPow[abs(g-l)].f)%m1)+m1)%m1, 
            ((hsh[rev][g].s-(hsh[rev][l].s*pPow[abs(g-l)].s)%m2)+m2)%m2};
}
int getRadii(int l, int r){ //radii is inclusive
    int low = 0, high = min(l+1, n-r);
    while (low < high){
        int mid = (low+high+1)/2;
        if (getHash(l-mid+1, l, 0) == getHash(r, r+mid-1, 1)) low = mid;
        else high = mid-1;
    }
    return low;
}

int main(){
    cin >> str; n = str.size(); pPow[0] = {1, 1};
    for (int i = 0; i < n; i++){
        hsh[0][i+1] = {(hsh[0][i].f*p+(str[i]-'a'+1))%m1, (hsh[0][i].s*p+(str[i]-'a'+1))%m2};
        hsh[1][n-i] = {(hsh[1][n-i+1].f*p+(str[n-i-1]-'a'+1))%m1, (hsh[1][n-i+1].s*p+(str[n-i-1]-'a'+1))%m2}; 
        pPow[i+1] = {(pPow[i].f*p)%m1, (pPow[i].s*p)%m2};
    }
    for (int i = 0; i < n; i++){
        for (int j = i; j < i+2; j++){
            int r = getRadii(i, j); ans += r;
            if (i-r >= 0 and j+r <= n){
                int add = 1+getRadii(i-r-1, j+r+1);
                create[i-r][str[j+r]-'a'] += add; 
                create[j+r][str[i-r]-'a'] += add;
            }
            if (r > 0){
                destroy[i-r+1].f++; destroy[j+r].f++; 
                destroy[i-r+1].s -= i-r; destroy[j+r].s -= j+r;
                destroy[j].f--; destroy[i+1].f--;
                destroy[j].s += i-r, destroy[i+1].s += j+r; 
            }
        }
    }
    ll change = 0, pos = 0, best = 0;
    for (int i = 0; i < n; i++){
        change += destroy[i].f; pos += destroy[i].s;
        for (int j = 0; j < 26; j++) 
            best = max(best, create[i][j]-(i*change+pos));
    }
    cout<<ans+best;
}

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