oj.uz

Submission #533830

# Submission time Handle Problem Language Result Execution time Memory
533830 2022-03-07T11:33:44 Z stefantaga Palinilap (COI16_palinilap) C++14
100 / 100
 120 ms 48804 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 332 KB Output is correct
2 Correct 0 ms 316 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 0 ms 332 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2764 KB Output is correct
2 Correct 4 ms 2712 KB Output is correct
3 Correct 5 ms 2764 KB Output is correct
4 Correct 3 ms 1740 KB Output is correct
5 Correct 5 ms 2364 KB Output is correct
6 Correct 5 ms 2764 KB Output is correct
7 Correct 5 ms 2760 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 48716 KB Output is correct
2 Correct 85 ms 48804 KB Output is correct
3 Correct 87 ms 48708 KB Output is correct
4 Correct 113 ms 48680 KB Output is correct
5 Correct 115 ms 48788 KB Output is correct
6 Correct 111 ms 48708 KB Output is correct
7 Correct 113 ms 48708 KB Output is correct
8 Correct 64 ms 48800 KB Output is correct
9 Correct 112 ms 48684 KB Output is correct
10 Correct 112 ms 48748 KB Output is correct
11 Correct 83 ms 48740 KB Output is correct
12 Correct 120 ms 48704 KB Output is correct
13 Correct 119 ms 48740 KB Output is correct
14 Correct 119 ms 48788 KB Output is correct
15 Correct 112 ms 48776 KB Output is correct
16 Correct 99 ms 48760 KB Output is correct
17 Correct 110 ms 48696 KB Output is correct
18 Correct 114 ms 48708 KB Output is correct
19 Correct 112 ms 48708 KB Output is correct