oj.uz

Submission #484253

# Submission time Handle Problem Language Result Execution time Memory
484253 2021-11-02T17:50:49 Z Vladth11 Palinilap (COI16_palinilap) C++14
0 / 100
 486 ms 50784 KB 
#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 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++;
        cnt += (i - st + (s[i] == '{')) / 2;
        st--;
        dr++;
        palindroame[st + 1]++;
        palindroame[dr]--;
        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) / 2 + 1;
        punctaj[dr][s[st] - 'a'] += (nd - dr) / 2 + 1;
    }
    ll best = 0;
    for(i = 1; i <= n; i++) {
        palindroame[i] += palindroame[i - 1];
        ll maxim = 0;
        for(ll j = 0; j < 26; j++) {
            maxim = max(maxim, punctaj[i][j]);
        }
        best = max(best, 1LL * (maxim - palindroame[i] + 1)); /// + 1 fiindca el tot ramane palindrom
    }
    cout << cnt + best - (n + 1) / 2;
    return 0;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2784 KB Output is correct
2 Incorrect 13 ms 2812 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Incorrect 486 ms 50784 KB Output isn't correct
2 Halted 0 ms 0 KB -