oj.uz

Submission #484268

# Submission time Handle Problem Language Result Execution time Memory
484268 2021-11-02T19:08:42 Z Vladth11 Palinilap (COI16_palinilap) C++14
100 / 100
 518 ms 51012 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 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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2764 KB Output is correct
2 Correct 12 ms 2764 KB Output is correct
3 Correct 15 ms 2784 KB Output is correct
4 Correct 8 ms 1788 KB Output is correct
5 Correct 11 ms 2380 KB Output is correct
6 Correct 14 ms 2764 KB Output is correct
7 Correct 14 ms 2764 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 50776 KB Output is correct
2 Correct 400 ms 50812 KB Output is correct
3 Correct 414 ms 50936 KB Output is correct
4 Correct 453 ms 50884 KB Output is correct
5 Correct 458 ms 50928 KB Output is correct
6 Correct 453 ms 50884 KB Output is correct
7 Correct 469 ms 50848 KB Output is correct
8 Correct 249 ms 5456 KB Output is correct
9 Correct 474 ms 50884 KB Output is correct
10 Correct 455 ms 50816 KB Output is correct
11 Correct 408 ms 50992 KB Output is correct
12 Correct 506 ms 50972 KB Output is correct
13 Correct 457 ms 50884 KB Output is correct
14 Correct 459 ms 51012 KB Output is correct
15 Correct 456 ms 50884 KB Output is correct
16 Correct 518 ms 50880 KB Output is correct
17 Correct 450 ms 50880 KB Output is correct
18 Correct 458 ms 50792 KB Output is correct
19 Correct 455 ms 50816 KB Output is correct