oj.uz

답안 #1022082

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1022082 2024-07-13T09:47:18 Z PVSekhar Palinilap (COI16_palinilap) C++17
100 / 100
 502 ms 38940 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, 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;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    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<int> p_cent[n];
    int l = 0, r = 0, mid, pos[n][26];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 26; j++) pos[i][j] = 0;
    }
    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); 
            pos[i + l][t[i - l] - 'a'] = 1;
            pos[i - l][t[i + l] - 'a'] = 1;
        }
        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 = 1; i < n; i+=2) {
        for (char x = 'a'; x <= 'z'; x++) {
            if (pos[i][x - 'a']) {
                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";
}

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1880 KB Output is correct
2 Correct 2 ms 1884 KB Output is correct
3 Correct 2 ms 1884 KB Output is correct
4 Correct 2 ms 1884 KB Output is correct
5 Correct 2 ms 1884 KB Output is correct

Subtask #2
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3676 KB Output is correct
2 Correct 6 ms 3676 KB Output is correct
3 Correct 11 ms 3672 KB Output is correct
4 Correct 9 ms 2908 KB Output is correct
5 Correct 11 ms 3492 KB Output is correct
6 Correct 12 ms 3768 KB Output is correct
7 Correct 19 ms 3676 KB Output is correct

Subtask #3
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 216 ms 38084 KB Output is correct
2 Correct 116 ms 38552 KB Output is correct
3 Correct 117 ms 37808 KB Output is correct
4 Correct 304 ms 37912 KB Output is correct
5 Correct 303 ms 37916 KB Output is correct
6 Correct 319 ms 37916 KB Output is correct
7 Correct 309 ms 37920 KB Output is correct
8 Correct 60 ms 34588 KB Output is correct
9 Correct 310 ms 37916 KB Output is correct
10 Correct 304 ms 38052 KB Output is correct
11 Correct 125 ms 38552 KB Output is correct
12 Correct 205 ms 38940 KB Output is correct
13 Correct 214 ms 37920 KB Output is correct
14 Correct 329 ms 37972 KB Output is correct
15 Correct 318 ms 37976 KB Output is correct
16 Correct 221 ms 38680 KB Output is correct
17 Correct 502 ms 37664 KB Output is correct
18 Correct 226 ms 37664 KB Output is correct
19 Correct 498 ms 37660 KB Output is correct