Submission #998511

#	Time	Username	Problem	Language	Result	Execution time	Memory
998511		fryingduc	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	135 ms	20840 KiB

palindromic

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

const int maxn = 1e6 + 6;
const int base = 31;
const int mod = 1e9 + 9;
string s;
int h[maxn], p[maxn];
int get_hash(int l, int r) {
    return (h[r] - (1ll * h[l - 1] * p[r - l + 1] % mod) + mod) % mod;
}
void solve() {
    cin >> s;
    int n = s.size();
    s = ' ' + s;
    for(int i = 1; i <= n; ++i) {
        h[i] = (1ll * h[i - 1] * base % mod + (s[i] - 'a' + 1)) % mod;
    }
    
    int l = 1, r = n;
    int res = 0;
    for(int i = 1; i <= n / 2; ++i) {
        if(l >= r) break;
        if(get_hash(l, i) == get_hash(r - (i - l), r)) {
            res += 2;
            r = r - (i - l) - 1;
            l = i + 1;
        }
    }
    if(l <= (n + 1) / 2) ++res;
    
    cout << res << '\n';
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    p[0] = 1;
    for(int i = 1; i < maxn; ++i) {
        p[i] = (1ll * p[i - 1] * base) % mod;
    }
    
    int tt; cin >> tt;
    while(tt--) {
        solve();
    }
    return 0;
}

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