Submission #550543

#	Time	Username	Problem	Language	Result	Execution time	Memory
550543		Jomnoi	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	66 ms	26672 KiB

palindromic

#include <bits/stdc++.h>
#define DEBUG false
using namespace std;

const int MAX_N = 1e6 + 10;
const long long P = 9973;
const long long MOD1 = 1e9 + 9;
const long long MOD2 = 1e9 + 7;

char s[MAX_N];
long long p1[MAX_N], p2[MAX_N];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t;
    cin >> t;
    p1[0] = p2[0] = 1;
    for(int i = 1; i < MAX_N; i++) {
        p1[i] = p1[i - 1] * P % MOD1;
        p2[i] = p2[i - 1] * P % MOD2;
    }
    while(t--) {
        cin >> (s + 1);
        int n = strlen(s + 1);
        for(int i = 1; i <= n; i++) {
            s[i] = s[i] - 'a' + 1;
        }

        int ans = 0;
        long long h1 = 0, h2 = 0, rh1 = 0, rh2 = 0;
        int i, j, l = 0, r = n + 1;
        for(i = 1, j = n; i < j; i++, j--) {
            h1 = (h1 * P + s[i]) % MOD1;
            h2 = (h2 * P + s[i]) % MOD2;
            rh1 = (rh1 + p1[r - j - 1] * s[j]) % MOD1;
            rh2 = (rh2 + p2[r - j - 1] * s[j]) % MOD2;

            if(h1 == rh1 and h2 == rh2) {
                ans += 2;
                l = i, r = j;
                h1 = h2 = rh1 = rh2 = 0;
            }
        }
        if((i - 1 != l and j + 1 != r) or n % 2 == 1) {
            ans++;
        }
        cout << ans << '\n';
    }
    return 0;
}

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