Submission #486790

#	Time	Username	Problem	Language	Result	Execution time	Memory
486790		mahdavifar	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	237 ms	20092 KiB

palindromic

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

const int maxn = 1000005;

const long long m    = 1000000007;
const long long p    = 999999893;
long long power[maxn] = {};

int main()
{
    // preprocess
    power[0] = 1;
    for (int i = 1; i < maxn; i++)
        power[i] = (power[i-1] * p) % m;

    // get number of test cases
    int T; cin >> T;

    // solve test cases
    for (int t = 0; t < T; t++)
    {
        string s; cin >> s;
        int n = s.length();

        int base = 0, ans = 0;
        long long hash1 = 0, hash2 = 0;

        for( int i=0, j=n-1; i < n-i; i++, j--)
        {
            hash1 = (hash1 + s[i] * power[i]) % m;
            hash2 = (hash2 + s[j] * power[j]) % m;

            if ((hash1 * power[j-base]) % m == hash2) {
                ans += 2 - (i == j);

                hash1 = hash2 = 0;
                base = i + 1;
            }
        }

        if (hash1 != 0)
            ans += 1;

        cout << ans << endl;
    }
}

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