oj.uz

Submission #331291

# Submission time Handle Problem Language Result Execution time Memory
331291 2020-11-28T00:41:02 Z thecodingwizard Palinilap (COI16_palinilap) C++11
54 / 100
 138 ms 28800 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];
int extra[210001][26];
ll numPalindromes[210001];
int deltaDelta[210001];

ll getHash(int a, int b, int c) {
    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;

        // 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++;

        int x = i-r-1, y = i+r+1;
        assert(s[0][x] != '#' && s[1][y] != '#');
        extra[x][s[0][y]-'a'] += (r2+1)/2;
        extra[y][s[0][x]-'a'] += (r2+1)/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 1772 KB Output is correct
2 Correct 5 ms 1772 KB Output is correct
3 Correct 6 ms 1772 KB Output is correct
4 Correct 3 ms 1260 KB Output is correct
5 Correct 5 ms 1516 KB Output is correct
6 Correct 5 ms 1772 KB Output is correct
7 Correct 5 ms 1772 KB Output is correct

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 28416 KB Output is correct
2 Correct 113 ms 28536 KB Output is correct
3 Correct 138 ms 28524 KB Output is correct
4 Correct 116 ms 28524 KB Output is correct
5 Correct 115 ms 28524 KB Output is correct
6 Correct 115 ms 28524 KB Output is correct
7 Correct 117 ms 28800 KB Output is correct
8 Correct 104 ms 28544 KB Output is correct
9 Correct 117 ms 28524 KB Output is correct
10 Correct 117 ms 28524 KB Output is correct
11 Correct 135 ms 28524 KB Output is correct
12 Correct 118 ms 28544 KB Output is correct
13 Correct 137 ms 28524 KB Output is correct
14 Correct 128 ms 28524 KB Output is correct
15 Correct 130 ms 28524 KB Output is correct
16 Incorrect 121 ms 28524 KB Output isn't correct
17 Halted 0 ms 0 KB -