oj.uz

Submission #331295

# Submission time Handle Problem Language Result Execution time Memory
331295 2020-11-28T01:15:44 Z thecodingwizard Palinilap (COI16_palinilap) C++11
100 / 100
 168 ms 48876 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define ii pair<int, int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define F0R(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define inf 1000000010

const ll M = 1e9+9, P = 9973;

int n;
string s[2];
ll hsh[2][210001];
ll pw[210001];
ll extra[210001][26];
ll numPalindromes[210001];
int deltaDelta[210001];

ll getHash(int a, int b, int c) {
    assert(a >= 0 && a < n && b >= 0 && b < n);
    if (c == 1) {
        int tmp = a;
        a = n-1 - b;
        b = n-1 - tmp;
    }
    return (hsh[c][b+1]-(hsh[c][a]*pw[b-a+1])%M+M)%M;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    string tmp; cin >> tmp;
    s[0].resize((int)tmp.size()*2+1);
    for (int i = 0; i < (int)tmp.size(); i++) {
        s[0][i*2] = '#';
        s[0][i*2+1] = tmp[i];
    }
    s[0][(int)tmp.size()*2] = '#';
    n = s[0].length();
    s[1] = s[0];
    reverse(all(s[1]));

    hsh[0][0] = 1;
    hsh[1][0] = 1;
    pw[0] = 1;
    F0R(i, n) {
        hsh[0][i+1] = ((hsh[0][i]*P)%M+s[0][i])%M;
        hsh[1][i+1] = ((hsh[1][i]*P)%M+s[1][i])%M;
        pw[i+1] = pw[i]*P%M;
    }

    ll base = 0;
    F0R(i, n) {
        // calculate radius of palindrome
        int lo = 0, hi = min(i, n-i-1)+1, r = 0;
        while (lo < hi) {
            int mid = (lo+hi)/2;
            bool valid = getHash(i-mid, i, 0) == getHash(i, i+mid, 1);

            if (valid) {
                r = mid;
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        if (r != 0) {
            deltaDelta[i-r]++;
            deltaDelta[i+1]-=2;
            deltaDelta[i+r+2]++;
        }
        base += (r+1)/2;
        F0R(j, 26) extra[i][j] += (r+1)/2;

        int x = i-r-1, y = i+r+1;
        if (x < 0 || x >= n || y < 0 || y >= n) continue;

        // fix the boundary, calculate the new radius of palindrome
        lo = 0, hi = min(i-r-1, n-(i+r+1)-1)+1; int r2 = 0;
        while (lo < hi) {
            int mid = (lo+hi)/2;
            bool valid = getHash(i-r-1-mid, i-r-2, 0) == getHash(i+r+2, i+r+1+mid, 1);

            if (valid) {
                r2 = mid;
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        r2++;

        assert(s[0][x] != '#' && s[1][y] != '#');
        extra[x][s[0][y]-'a'] += r2/2;
        extra[y][s[0][x]-'a'] += r2/2;
    }

    ll delta = 0, tot = 0;
    F0R(i, n) {
        delta += deltaDelta[i];
        tot += delta;
        numPalindromes[i] = tot/2;
    }

    ll best = 0;
    F0R(i, n) {
        if (i%2 == 1) {
            F0R(j, 26) {
                best = max(best, extra[i][j] - numPalindromes[i]);
            }
        }
    }
    cout << base+best << endl;

    return 0;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2796 KB Output is correct
2 Correct 5 ms 2796 KB Output is correct
3 Correct 7 ms 2796 KB Output is correct
4 Correct 4 ms 1772 KB Output is correct
5 Correct 6 ms 2412 KB Output is correct
6 Correct 7 ms 2796 KB Output is correct
7 Correct 7 ms 2796 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 48748 KB Output is correct
2 Correct 119 ms 48768 KB Output is correct
3 Correct 122 ms 48764 KB Output is correct
4 Correct 165 ms 48748 KB Output is correct
5 Correct 159 ms 48876 KB Output is correct
6 Correct 158 ms 48876 KB Output is correct
7 Correct 159 ms 48748 KB Output is correct
8 Correct 96 ms 48876 KB Output is correct
9 Correct 159 ms 48748 KB Output is correct
10 Correct 160 ms 48748 KB Output is correct
11 Correct 138 ms 48748 KB Output is correct
12 Correct 167 ms 48876 KB Output is correct
13 Correct 168 ms 48748 KB Output is correct
14 Correct 165 ms 48748 KB Output is correct
15 Correct 160 ms 48712 KB Output is correct
16 Correct 146 ms 48748 KB Output is correct
17 Correct 157 ms 48876 KB Output is correct
18 Correct 161 ms 48876 KB Output is correct
19 Correct 156 ms 48876 KB Output is correct