제출 #741952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
741952		Sharky	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	74 ms	28484 KiB

palindromic

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

#define int long long

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';
}

int32_t 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: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40