Submission #484268

#	Time	Username	Problem	Language	Result	Execution time	Memory
484268		Vladth11	Palinilap (COI16_palinilap)	C++14	100 / 100	518 ms	51012 KiB

palinilap

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 200005;
const ll VMAX = 21;
const ll INF = 2e9;
const ll MOD = 1000000009;
const ll BLOCK = 318;
const ll base = 31;
const ll nr_of_bits = 21;

char s[NMAX];
string ii;
ll hashes[NMAX], n, cnt;
ll hashesd[NMAX];
ll punctaj[NMAX][29];
ll palindroame[NMAX];
ll cn[NMAX];

ll lgput(ll n, ll p) {
    ll r = 1;
    while(p) {
        if(p & 1) {
            r *= n;
            r %= MOD;
        }
        n *= n;
        n %= MOD;
        p /= 2;
    }
    return r;
}

ll invmod(ll x) {
    return lgput(x, MOD - 2);
}

ll gethash(ll i, ll j) {
    if(i > j)
        swap(i, j);
    return ((hashes[j] - (hashes[i - 1] * lgput(base, (j - i + 1))) % MOD + MOD) % MOD); /// poate i - 2
}

ll gethashdr(ll i, ll j) {
    if(i < j)
        swap(i, j);
    return (hashesd[j] - (hashesd[i + 1] * lgput(base, (i - j + 1))) % MOD + MOD) % MOD; /// poate i - 2
}

int main() {
    ll  i;
    cin >> ii;
    n = ii.size();
    for(i = 1; i <= n * 2 + 1; i++) {
        if(i % 2 == 0) {
            s[i] = ii[i / 2 - 1];
        } else {
            s[i] = 'z' + 1;
        }
    }
    n = n * 2 + 1;
    for(i = 1; i <= n; i++) {
        hashes[i] = (hashes[i - 1] * base) % MOD + (s[i] - 'a' + 1);
        hashes[i] %= MOD;
    }
    for(i = n; i >= 1; i--) {
        hashesd[i] = (hashesd[i + 1] * base) % MOD + (s[i] - 'a' + 1);
        hashesd[i] %= MOD;
    }
    for(i = 1; i <= n; i++) {
        ll r = 0, pas = (1 << nr_of_bits);
        while(pas) {
            ll nou = r + pas;
            if(i - nou >= 1 && i + nou <= n && gethash(i - nou, i) == gethashdr(i, i + nou))
                r = nou;
            pas /= 2;
        }
        ll st = i - r;
        ll dr = i + r;
        cnt += (i - st + (s[i] == '{') + 1) / 2;
        if(i % 2 == 0)
            cn[i / 2] = (i - st + (s[i] == '{') + 1) / 2;
        st--;
        dr++;
        if(i % 2 == 0){
            palindroame[(st + 2) / 2]++;
            palindroame[i / 2 + 1]--;
            palindroame[i / 2 + 1]--;
            palindroame[dr / 2 + 1]++; /// sau pe 1
        }else{
            palindroame[(st + 2) / 2]++;
            palindroame[(i + 1) / 2]--;
            palindroame[(i + 1) / 2 + 1]--;
            palindroame[dr / 2 + 1]++;
        }
        if(st == 0)
            continue;
        if(dr == n + 1)
            continue;
        r = 0, pas = (1 << nr_of_bits);
        while(pas) {
            ll nst = st - (r + pas);
            ll ndr = dr + (r + pas);
            if(nst >= 1 && ndr <= n && gethash(nst, st - 1) == gethashdr(dr + 1, ndr))
                r += pas;
            pas /= 2;
        }
        ll ns = st - r;
        ll nd = dr + r;
        punctaj[st][s[dr] - 'a'] += (st - ns + 1) / 2;
        punctaj[dr][s[st] - 'a'] += (nd - dr + 1) / 2;
    }
    ll best = 0;
    for(i = 1; i <= n / 2; i++){
        palindroame[i] += palindroame[i - 1];
    }
    for(i = 1; i <= n / 2; i++) {
        palindroame[i] += palindroame[i - 1];
        ll maxim = 0;
        for(ll j = 0; j < 26; j++) {
            maxim = max(maxim, punctaj[i * 2][j]);
        }
        best = max(best, 1LL * (maxim - palindroame[i] + cn[i])); /// + 1 fiindca alea cu mijlocul in el raman tot palindrom
    }
    cout << cnt + best - (n + 1) / 2;
    return 0;
}

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