oj.uz

Submission #1021796

# Submission time Handle Problem Language Result Execution time Memory
1021796 2024-07-13T05:27:05 Z PVSekhar Palinilap (COI16_palinilap) C++17
0 / 100
 1000 ms 66512 KB 
#include <bits/stdc++.h>
using namespace std; 
#define ll long long
const int MOD = 1e9 + 7;
const int N = 2e5 + 2;
const int P = 31;

string s, t = "{";
ll n, pref[N], suff[N], p_pow[N], diff[N];
int palin[N], c_ind, c_val;

void comp_pref() {
    pref[0] = suff[0] = 0;
    for (int i = 1; i <= n; i++) {
        pref[i] = (pref[i - 1] + ((t[i - 1] - 'a' + 1) * p_pow[i - 1] % MOD)) % MOD;
        suff[i] = (suff[i - 1] + ((t[n - i] - 'a' + 1) * p_pow[i - 1] % MOD)) % MOD;
    }
}

bool check_palin(int i, int len, int change) {
    ll val1 = MOD + pref[i + len] - pref[i - len + 1], p1 = i - len + 1, val2 = MOD + suff[n - i + len - 1] - suff[n - i - len], p2 = n - i - len;
    if (change) {
        val1 = MOD + val1 + (c_val * p_pow[c_ind] % MOD);
        val2 = MOD + val2 + (c_val * p_pow[n - c_ind - 1] % MOD);
    }
    val1 %= MOD, val2 %= MOD;
    if (p1 > p2) val2 *= p_pow[p1 - p2], val2 %= MOD;
    else val1 *= p_pow[p2 - p1], val1 %= MOD;
    if (val1 == val2) return true;
    return false;
}

void solve() {
    p_pow[0] = 1;
    for (int i = 1; i < N; i++) p_pow[i] = p_pow[i-1] * P % MOD;
    ll ans = 0, m_val = 0;
    cin >> s;
    for (char x : s) t += x, t += '{';
    n = t.length();
    for (int i = 0; i <= n; i++) diff[i] = 0;
    comp_pref();
    vector<vector<ll>> val(n, vector<ll> (26, 0)), p_cent(n);
    int l = 0, r = 0, mid;
    for (int i = 0; i < n; i++) {
        l = 1, r = n+1;
        while (r - l > 1) {
            mid = (l + r) / 2;
            if (i + mid - 1 < n && i - mid + 1 >= 0 && check_palin(i, mid, 0)) {
                l = mid;
            } else {
                r = mid;
            }
        }
        palin[i] = l;
        if (i - l >= 0 && i + l < n) p_cent[i - l].push_back(i), p_cent[i + l].push_back(i); 
    }
    for (int i = 0; i < n; i++) ans += palin[i] / 2;
    for (int i = 0; i < n; i++) {
        for (char x = 'a'; x <= 'z'; x++) {
            c_ind = i, c_val = x - t[i];
            for (int ind : p_cent[i]) {
                l = palin[ind], r = n+1;
                while (r - l > 1) {
                    mid = (l + r) / 2;
                    if (ind + mid - 1 < n && ind - mid + 1 >= 0 && check_palin(ind, mid, 1)) {
                        l = mid;
                    } else {
                        r = mid;
                    }
                }
                val[i][x - 'a'] += l / 2 - palin[ind] / 2;
                // cout << ind << " " << l << " " << palin[ind] << " " << x << "\n";
            }
            m_val = max(m_val, val[i][x - 'a']);
        }
    }
    cout << ans + m_val << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t;
    t = 1;
    // cin >> t;
    while(t--) {
        solve();
    }
    return 0;  
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5212 KB Output is correct
2 Incorrect 42 ms 5212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1061 ms 66512 KB Time limit exceeded
2 Halted 0 ms 0 KB -