oj.uz

Submission #331294

# Submission time Handle Problem Language Result Execution time Memory
331294 2020-11-28T01:14:47 Z thecodingwizard Palinilap (COI16_palinilap) C++11
54 / 100
 181 ms 28524 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) {
    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 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 4 ms 1260 KB Output is correct
5 Correct 7 ms 1536 KB Output is correct
6 Correct 6 ms 1772 KB Output is correct
7 Correct 6 ms 1772 KB Output is correct

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 28408 KB Output is correct
2 Correct 108 ms 28412 KB Output is correct
3 Correct 108 ms 28396 KB Output is correct
4 Correct 146 ms 28396 KB Output is correct
5 Correct 181 ms 28396 KB Output is correct
6 Correct 149 ms 28396 KB Output is correct
7 Correct 148 ms 28376 KB Output is correct
8 Correct 82 ms 28396 KB Output is correct
9 Correct 164 ms 28396 KB Output is correct
10 Correct 146 ms 28400 KB Output is correct
11 Correct 108 ms 28396 KB Output is correct
12 Correct 179 ms 28524 KB Output is correct
13 Correct 156 ms 28396 KB Output is correct
14 Correct 147 ms 28524 KB Output is correct
15 Correct 149 ms 28352 KB Output is correct
16 Incorrect 135 ms 28396 KB Output isn't correct
17 Halted 0 ms 0 KB -