Submission #741951

#	Time	Username	Problem	Language	Result	Execution time	Memory
741951		Sharky	Palindromic Partitions (CEOI17_palindromic)	C++17	0 / 100	17 ms	8276 KiB

palindromic

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

const int mod = 1e9 + 7;
const int mod2 = 998244353;
const int maxn = 1E6 + 1;

vector<int> p1(maxn, 1), p2(maxn, 1);

void solve() {
    string s;
    cin >> s;
    int n = s.length(), ans = 0;
    int l = 0, r = n - 1, l1 = 0, r1 = 0, l2 = 0, r2 = 0, cnt = 0;
    bool jn = true;
    while (l <= r) {
        jn = false;
        l1 = (l1 + (s[l] - 'a' + 1) * p1[cnt]) % mod;
        l2 = (l2 + (s[l] - 'a' + 1) * p2[cnt]) % mod2;
        r1 = (r1 * 27 + (s[r] - 'a' + 1)) % mod;
        r2 = (r2 * 27 + (s[r] - 'a' + 1)) % mod2;
        cnt++;
        if (l1 == r1 && l2 == r2) {
            ans += ((l == r) ? 1 : 2);
            l1 = 0, r1 = 0, l2 = 0, r2 = 0, cnt = 0;
            jn = true;
        }
        l++, r--;
    }
    if (!jn) ans++;
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t;
    cin >> t;
    for (int i = 1; i <= 1e6; i++) {
        p1[i] = (p1[i-1] * 27) % mod;
        p2[i] = (p2[i-1] * 27) % mod2;
    }
    while (t--) solve();
}

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