제출 #1225804

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1225804		giorgi123glm	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	34 ms	3216 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 + 7;

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 / 2; i++) {
            hash1 = (31 * hash1) + (str[i] - 'a');
            hash1 %= mod;

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

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

            // cout << i << ' ' << ans << ' ' << hash1 << ' ' << hash2 << '\n';
        }
        
        if (N % 2 == 0) {
            if (hash1 != 0 || hash2 != 0)
                ans++;
        } else if (N % 2 == 1) {
            if (hash1 != 0 || hash2 != 0)
                ans++;
            else
                ans++;
        }

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

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