Submission #1022029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022029		PVSekhar	Palinilap (COI16_palinilap)	C++17	54 / 100	1061 ms	17696 KiB

palinilap

#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, st[N], en[N];

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, val;
    cin >> s;
    for (char x : s) t += x, t += '{';
    n = t.length();
    for (int i = 0; i <= n; i++) diff[i] = st[i] = en[i] = 0;
    comp_pref();
    vector<vector<int>> 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); 
        ans += palin[i] / 2;
    }
    ll cnt = 0, sum = 0;
    for (int i = 0; i < n; i++) {
        if (i&1) {
            diff[i] = sum;
            sum -= cnt;
            cnt++;
            sum += (palin[i] - 1) / 2;
            st[i - palin[i] + 1]++, en[i + palin[i] - 1]++;
        } else {
            cnt++;
            sum += palin[i] / 2;
            st[i - palin[i] + 1]++, en[i + palin[i] - 1]++;
            cnt -= en[i];
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        if (i&1) {
            diff[i] += sum;
            sum -= cnt;
            cnt++;
            sum += (palin[i] - 1) / 2;
        } else {
            cnt++;
            sum += palin[i] / 2;
            cnt -= st[i];
        }
    }
    // for (int i = 0; i < n; i++) cout << diff[i] << " ";
    // cout << "\n";
    for (int i = 0; i < n; i++) {
        if (!(i&1)) continue;
        for (char x = 'a'; x <= 'z'; x++) {
            c_ind = i, c_val = x - t[i], val = 0;
            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 += l / 2 - palin[ind] / 2;
                // cout << ind << " " << l << " " << palin[ind] << " " << x << "\n";
            }
            m_val = max(m_val, val - diff[i]);
        }
    }
    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: 17 / 17
• Subtask 2: 37 / 37
• Subtask 3: 0 / 46