Submission #242039

#	Time	Username	Problem	Language	Result	Execution time	Memory
242039		parsa_mobed	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	103 ms	20584 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 10, B1 = 619, B2 = 787;
int H1[N], H2[N], pw1[N], pw2[N];

pair <int , int> HASH(int l, int r)
{
    return {H1[r] - H1[l - 1] * pw1[r - l + 1] , H2[r] - H2[l - 1] * pw2[r - l + 1]};
}

void Main()
{
    memset(H1, 0, sizeof H1);
    memset(H2, 0, sizeof H2);
    string s; cin >> s;
    int n = s.size();
    for (int i = 1; i <= n; i ++) {
        H1[i] = H1[i - 1] * B1 + (s[i - 1] - 'a' + 17);
        H2[i] = H2[i - 1] * B2 + (s[i - 1] - 'a' + 33);
    }
    int ans = 0;
    int l = 1;
    for (int i = 1; i <= n / 2; i ++) {
        if (HASH(l, i) == HASH(n - i + 1, n - l + 1)) {
            ans+=2;
            l = i + 1;
        }
    }
    cout << ans + ((l - 1) * 2 < n) << "\n";
    return ;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    pw1[0] = pw2[0] = 1;
    for (int i = 1; i < N; i ++) pw1[i] = pw1[i - 1] * B1, pw2[i] = pw2[i - 1] * B2;
    int t; cin >> t;
    while (t--) {
        Main();
    }
}
/*
testcase
4
bonobo
deleted
racecar
racecars
*/

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