Submission #1225781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225781		giorgi123glm	Palindromic Partitions (CEOI17_palindromic)	C++20	0 / 100	0 ms	320 KiB

palindromic

#include <initializer_list>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <algorithm>
#include <functional>
#include <fstream>
using namespace std;

#define int long long

const int mod = 1e9 + 9;

signed main () {
    ios::sync_with_stdio (false);
    cin.tie (0);
    cout.tie (0);

    int t = 0;
    cin >> t;

    while (t--) {
        string str;
        cin >> str;

        int N = str.size();
        str = " " + str;

        int hash1 = 0;
        int hash2 = 0;
        int pow = 1;

        int ans = 0;
        for (int i = 1; i <= (N + 1) / 2; i++) {
            hash1 = (26 * hash1) + (str[i] - 'a');
            hash1 %= mod;

            hash2 += (str[N - i + 1] - 'a') * pow;
            pow *= 26, pow %= mod;
            hash2 %= mod;

            if (hash1 == hash2) {
                ans += 2;
                hash1 = hash2 = 0;
                pow = 1;
            }
        }

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

        ans--;

        cout << ans << '\n';
    }
}

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