Submission #655906

#	Time	Username	Problem	Language	Result	Execution time	Memory
655906		gozonite	Palinilap (COI16_palinilap)	C++14	100 / 100	323 ms	26576 KiB

palinilap

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <deque>
#include <queue>
#include <tuple>
#include <cmath>
#include <cctype>
#include <stack>
#include <cassert>
#include <iomanip>
#include <random>
using namespace std;
using ll = long long;
ll M = 1e9 + 7, P = 31;

string s;
int n;
ll power[100000][26]={}; // how many new palindromes can be made if index i is changed to char c in power[i][c]
ll rsum[100000]={}, lsum[100000]={}, rsump[100000]={}, lsump[100000]={};
ll P2[100000];
ll hpref[100000], hsuff[100000];

ll get_hash(int a, int b) {
    if (a == 0) return hpref[b];
    return ((hpref[b] - P2[b-a+1]*hpref[a-1])%M + M) % M;
}
ll rev_hash(int a, int b) {
    if (b == n-1) return hsuff[a];
    return ((hsuff[a] - P2[b-a+1]*hsuff[b+1])%M + M) % M;
}

ll add(int ctr, bool even) { //cout << "eval: " << ctr << " " << even << endl;
    ll res = 0;
    int lc = ctr, rc = ctr + even;

    int lo = 0, hi = min(lc+1, n-rc);
    while (lo < hi) {
        int mid = (lo+hi+1)/2;
        if (get_hash(rc, rc+mid-1) == rev_hash(lc-mid+1, lc)) lo = mid;
        else hi = mid-1;
    }
    res += lo;
    if (lc+1 < n) {
        rsum[lc+1] += lo + (even ? 0 : -1), rsump[lc+1]++;
        if (rc+lo < n) rsump[rc+lo]--;
    }
    if (rc-1 >= 0) {
        lsum[rc-1] += lo + (even ? 0 : -1), lsump[rc-1]++;
        if (lc-lo >= 0) lsump[lc-lo]--;
    }

    ll val = lo;
    // cout << "value: " << val << endl;
    // update powers
    if (lc-val < 0 || rc+val >= n) return res;
    
    // update right end
    ll dc = s[lc-val]-s[rc+val];
    lo = val+1, hi = min(lc+1, n-rc);
    while (lo < hi) {
        int mid = (lo+hi+1)/2;
        ll rh = (get_hash(rc, rc+mid-1) + dc*P2[mid-1-val] + (M<<5LL)) % M;
        ll lh = rev_hash(lc-mid+1, lc);
        if (rh == lh) lo = mid;
        else hi = mid-1;
    }
    power[rc+val][s[lc-val]-'a'] += lo-val;
    // cout << "rval: " << power[rc+val][s[lc-val]-'a'] << endl;

    // update left end
    dc = s[rc+val]-s[lc-val];
    lo = val+1, hi = min(lc+1, n-rc);
    while (lo < hi) {
        int mid = (lo+hi+1)/2;
        ll rh = get_hash(rc, rc+mid-1);
        ll lh = (rev_hash(lc-mid+1, lc) + dc*P2[mid-1-val] + (M<<5LL)) % M;
        //cout << "left bs: " << mid << " " << rh << " " << lh << endl;
        if (rh == lh) lo = mid;
        else hi = mid-1;
    }
    //cout << "updated left end: " << dc << " " << lo << endl;

    power[lc-val][s[rc+val]-'a'] += lo-val;
    // cout << "lval: " << power[lc-val][s[rc+val]-'a'] << endl;

    return res;
}

int main() {
    cin >> s;
    n = s.size();
    P2[0] = 1;
    for (int i = 1; i < n; i++) P2[i] = P2[i-1] * P % M;
    hpref[0] = s[0]-'a', hsuff[n-1] = s[n-1]-'a';
    for (int i = 1; i < n; i++) hpref[i] = (hpref[i-1]*P + ll(s[i]-'a')) % M;
    for (int i = n-2; i >= 0; i--) hsuff[i] = (hsuff[i+1]*P + ll(s[i]-'a')) % M;

    // cout << "Debugging forward and reverse hashes: " << endl;
    // cout << get_hash(3, 4) << " " << rev_hash(3, 4) << endl;

    ll ans = 0;
    // odd palindromes
    for (int i = 0; i < n; i++) {
        ans += add(i, 0);
        ans += add(i, 1);
    }
    // cout << "pre ans: " << ans << endl;
    // for (int i = 0; i < n; i++) cout << lsum[i] << " "; cout << endl;
    // for (int i = 0; i < n; i++) cout << rsum[i] << " "; cout << endl;
    // for (int i = 0; i < n; i++) cout << lsump[i] << " "; cout << endl;
    // for (int i = 0; i < n; i++) cout << rsump[i] << " "; cout << endl;
    
    ll ds = 0, cnt = 0;
    // carry out psums
    for (int i = 0; i < n; i++) {
        ds -= cnt;
        ds += rsum[i], cnt += rsump[i];
        rsum[i] = ds;
    }
    ds = 0, cnt = 0;
    for (int i = n-1; i >= 0; i--) {
        ds -= cnt;
        ds += lsum[i], cnt += lsump[i];
        lsum[i] = ds;
    }

    // cout << "Debugging new lsum, rsum, lsump, rsump: " << endl;
    // for (int i = 0; i < n; i++) cout << lsum[i] << " "; cout << endl;
    // for (int i = 0; i < n; i++) cout << rsum[i] << " "; cout << endl;

    ll dans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 26; j++) {
            dans = max(dans, power[i][j] - lsum[i] - rsum[i]);
        }
    }
    cout << ans+dans << endl;

}

• Subtask 1: 17 / 17
• Subtask 2: 37 / 37
• Subtask 3: 46 / 46