Submission #571660

#	Time	Username	Problem	Language	Result	Execution time	Memory
571660		piOOE	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	58 ms	16736 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;

#define sz(x) ((int)size(x))
#define all(x) begin(x), end(x)
#define trace(x) cout << #x << ": " << (x) << endl;

typedef long long ll;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }

const int N = 1000001, mod = 998244353, X = 131;

int pw[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    pw[0] = 1;
    for (int i = 1; i < N; ++i)
        pw[i] = pw[i - 1] * (ll)X % mod;
    int test = 1;
    cin >> test;
    while (test--) {
        string s;
        cin >> s;
        int sumB = 0, sumE = 0, siz = 0;
        int n = sz(s);
        int ans = 0;
        for (int i = 0; i < n / 2; ++i) {
            ++siz;
            sumB = (sumB + pw[siz - 1] * (ll)s[i]) % mod;
            sumE = (sumE * (ll)X + s[n - i - 1]) % mod;
            if (sumB == sumE) {
                ans += 2;
                sumB = sumE = siz = 0;
            }
        }
        if (siz || 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