Submission #867826

#	Time	Username	Problem	Language	Result	Execution time	Memory
867826		phongcd	Palinilap (COI16_palinilap)	C++14	0 / 100	2 ms	348 KiB

palinilap

#include <bits/stdc++.h>
#define ll long long
#define ld long  double
#define ull unsigned long long
#define ii pair <int, int>
#define ill pair <ll, ll>
#define ild pair <ld, ld>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define file "test"
using namespace std;
const int N = 1e5 + 2;
const int M = 40;
const ll MOD = 1e9 + 7;
const ll INF = 3e18;
const ll base = 311;
const ll base2 = 1e4 + 7;
const int BLOCK_SIZE = 400;

int n;
ll pw[N], h[N];
ll f[N][26], bad[N];

ll get(int i, int j) {
    return (h[j] - h[i - 1] * pw[j - i + 1] + MOD * MOD) % MOD;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE 
        freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
    #endif

    string s; cin >> s;
    n = s.size();
    s = " " + s;

    pw[0] = 1;
    for (int i = 1; i <= n; i ++) {
        pw[i] = (pw[i - 1] * base) % MOD;
        h[i] = (h[i - 1] * base + s[i]) % MOD;
    }

    ll sum = 0;
    for (int i = 1; i <= n; i ++) {
        int l = 0, r = min(i - 1, n - i);
        while (l < r) {
            int mid = l + (r - l + 1) / 2;
            if (get(i - mid, i) == get(i, i + mid)) 
                l = mid;
            else r = mid - 1;
        }
        
        sum += l + 1;
        for (int c = 0; c < 26; c ++) f[i][c] += l + 1;
        bad[i - l] ++, bad[i + l + 1] --;

        if (1 < i - l && i + l < n) {
            f[i - l - 1][s[i + l + 1] - 'a'] ++;
            f[i + l + 1][s[i - l - 1] - 'a'] ++;
        }

        int x = l, L = i - l - 2, R = i + l + 2;
        if (L < 1 || R > n) continue;

        l = 0, r = min(L - 1, n - R);
        while (l < r) {
            int mid = l + (r - l + 1) / 2;
            if (get(L - mid, L) == get(R, R + mid))
                l = mid;
            else r = mid - 1;
        }

        if (get(L - l, L) == get(R, R + l)) {
            f[i - x - 1][s[i + x + 1] - 'a'] += l + 1;
            f[i + x + 1][s[i - x - 1] - 'a'] += l + 1;
        }
    }

    for (int i = 1; i < n; i ++) {
        int l = 0, r = min(i - 1, n - i);
        while (l < r) {
            int mid = l + (r - l + 1) / 2;
            if (get(i - mid, i) == get(i + 1, i + 1 + mid)) 
                l = mid;
            else r = mid - 1;
        }

        if (get(i - l, i) == get(i + 1, i + 1 + l)) {
            sum += l + 1;
            bad[i - l] ++, bad[i + l + 2] --;
        }
        else l --;

        if (1 < i - l && i + l + 1 < n) {
            f[i - l - 1][s[i + l + 2] - 'a'] ++;
            f[i + l + 2][s[i - l - 1] - 'a'] ++;
        }

        int x = l, L = i - l - 2, R = i + l + 3;
        if (L < 1 || R > n) continue;

        l = 0, r = min(L - 1, n - R);
        while (l < r) {
            int mid = l + (r - l + 1) / 2;
            if (get(L - mid, L) == get(R, R + mid))
                l = mid;
            else r = mid - 1;
        }

        if (get(L - l, L) == get(R, R + l)) {
            f[i - x - 1][s[i + x + 2] - 'a'] += l + 1;
            f[i + x + 2][s[i - x - 1] - 'a'] += l + 1;
        }
    }

    ll ans = sum, cur = 0;
    for (int i = 1; i <= n; i ++) {
        cur += bad[i];
        for (int c = 0; c < 26; c ++)
            ans = max(ans, sum + f[i][c] - cur);
    }
    cout << ans;
}
/*
     /\_/\ zzZ
    (= -_-)
    / >u  >u
*/

Compilation message (stderr)

palinilap.cpp: In function 'int main()':
palinilap.cpp:32:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
palinilap.cpp:32:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
      |                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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