Submission #115223

#	Time	Username	Problem	Language	Result	Execution time	Memory
115223		minhtung0404	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	134 ms	21024 KiB

palindromic

//https://oj.uz/problem/view/CEOI17_palindromic

#include<bits/stdc++.h>
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
using namespace std;

int t, h[N], po[N];
string s;

int get(int l, int r){
    return (h[r] - 1LL * h[l-1] * po[r-l+1] + 1LL * mod * mod) % mod;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    po[0] = 1;
    for (int i = 1; i < N; i++) po[i] = 53LL * po[i-1] % mod;
    cin >> t;
    while (t--){
        cin >> s;
        int n = s.size(); s = '.' + s;
        for (int i = 1; i <= n; i++) h[i] = (53LL * h[i-1] + s[i] - 'a') % mod;
        int l = 1, r = n, ans = 0;
        while (l <= r){
            bool ck = false;
            for (int i = l; i < r; i++){
                if (get(l, i) == get(n+1-i, r)){
                    l = i+1, r = n-i;
                    ans += 2;
                    ck = true;
                    break;
                }
            }
            if (!ck) {
                ans++;
                break;
            }
        }
        cout << ans << "\n";
    }
}

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