oj.uz

Submission #418659

# Submission time Handle Problem Language Result Execution time Memory
418659 2021-06-05T16:54:41 Z SirCovidThe19th Palinilap (COI16_palinilap) C++14
100 / 100
 213 ms 27304 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define f first
#define s second

const int mx = 1e5+5, p = 5281, m1 = 1e9+7, m2 = 1e9+9;

int n; string str; 
pair<ll, ll> pPow[mx], hsh[2][mx]; 
ll create[mx][26]; pair<ll, ll> destroy[mx]; ll ans;

pair<ll, ll> getHash(int l, int g, int rev){ //hsh is 1 indexed, paraters are 0 indexed
    l++; g++; int dir[2] = {-1, 1}; if (rev == 1) swap(l, g); l += dir[rev];
    return {((hsh[rev][g].f-(hsh[rev][l].f*pPow[abs(g-l)].f)%m1)+m1)%m1, 
            ((hsh[rev][g].s-(hsh[rev][l].s*pPow[abs(g-l)].s)%m2)+m2)%m2};
}
int getRadii(int l, int r){ //radii is inclusive
    int low = 0, high = min(l+1, n-r);
    while (low < high){
        int mid = (low+high+1)/2;
        if (getHash(l-mid+1, l, 0) == getHash(r, r+mid-1, 1)) low = mid;
        else high = mid-1;
    }
    return low;
}

int main(){
    cin >> str; n = str.size(); pPow[0] = {1, 1};
    for (int i = 0; i < n; i++){
        hsh[0][i+1] = {(hsh[0][i].f*p+(str[i]-'a'+1))%m1, (hsh[0][i].s*p+(str[i]-'a'+1))%m2};
        hsh[1][n-i] = {(hsh[1][n-i+1].f*p+(str[n-i-1]-'a'+1))%m1, (hsh[1][n-i+1].s*p+(str[n-i-1]-'a'+1))%m2}; 
        pPow[i+1] = {(pPow[i].f*p)%m1, (pPow[i].s*p)%m2};
    }
    for (int i = 0; i < n; i++){
        for (int j = i; j < i+2; j++){
            int r = getRadii(i, j); ans += r;
            if (i-r >= 0 and j+r <= n){
                int add = 1+getRadii(i-r-1, j+r+1);
                create[i-r][str[j+r]-'a'] += add; 
                create[j+r][str[i-r]-'a'] += add;
            }
            if (r > 0){
                destroy[i-r+1].f++; destroy[j+r].f++; 
                destroy[i-r+1].s -= i-r; destroy[j+r].s -= j+r;
                destroy[j].f--; destroy[i+1].f--;
                destroy[j].s += i-r, destroy[i+1].s += j+r; 
            }
        }
    }
    ll change = 0, pos = 0, best = 0;
    for (int i = 0; i < n; i++){
        change += destroy[i].f; pos += destroy[i].s;
        for (int j = 0; j < 26; j++) 
            best = max(best, create[i][j]-(i*change+pos));
    }
    cout<<ans+best;
}

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 304 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 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 5 ms 1612 KB Output is correct
2 Correct 6 ms 1612 KB Output is correct
3 Correct 8 ms 1612 KB Output is correct
4 Correct 5 ms 1128 KB Output is correct
5 Correct 7 ms 1356 KB Output is correct
6 Correct 8 ms 1584 KB Output is correct
7 Correct 9 ms 1612 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 27108 KB Output is correct
2 Correct 150 ms 27268 KB Output is correct
3 Correct 150 ms 27196 KB Output is correct
4 Correct 201 ms 27136 KB Output is correct
5 Correct 204 ms 27116 KB Output is correct
6 Correct 204 ms 27164 KB Output is correct
7 Correct 200 ms 27204 KB Output is correct
8 Correct 116 ms 27196 KB Output is correct
9 Correct 204 ms 27124 KB Output is correct
10 Correct 201 ms 27204 KB Output is correct
11 Correct 142 ms 27092 KB Output is correct
12 Correct 213 ms 27076 KB Output is correct
13 Correct 210 ms 27216 KB Output is correct
14 Correct 203 ms 27204 KB Output is correct
15 Correct 205 ms 27132 KB Output is correct
16 Correct 179 ms 27304 KB Output is correct
17 Correct 199 ms 27176 KB Output is correct
18 Correct 210 ms 27136 KB Output is correct
19 Correct 202 ms 27096 KB Output is correct