Submission #637714

#	Time	Username	Problem	Language	Result	Execution time	Memory
637714		tvladm2009	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	183 ms	10984 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int MAX_N = 1e6;
const int B = 257;
const int P = 1e9 + 7;

int prefH[MAX_N + 1], powerB[MAX_N + 1];

int rangeHash(int l, int r) {
    return (prefH[r] - prefH[l - 1] * 1LL * powerB[r - l + 1] % P + P) % P;
}

void solve(string s) {
    int n = s.size();
    for (int i = 1; i <= n; i++) {
        prefH[i] = (prefH[i - 1] * 1LL * B + (ll)s[i - 1]) % P;
    }
    powerB[0] = 1;
    for (int i = 1; i <= n; i++) {
        powerB[i] = powerB[i - 1] * 1LL * B % P;
    }
    int l = 1, r = n, ans = 0;
    int len = 0;
    while (l < r) {
        len++;
        if (rangeHash(l - len + 1, l) == rangeHash(r, r + len - 1)) {
            ans += 2;
            len = 0;
        }
        l++;
        r--;
    }
    if (len != 0 || l == r) {
        ans++;
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        solve(s);
    }

    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40