Submission #1114907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114907		vladilius	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	328 ms	27812 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
const int base = 31;

int f(char x){
    return x - 'a' + 1;
}

struct hash_str{
    vector<ll> pm, hm;
    void init(string s){
        int n = (int) s.length();
        pm.resize(n + 1);
        pm[0] = 1;
        for (int i = 1; i <= n; i++){
            pm[i] = (pm[i - 1] * base) % mod;
        }
        hm.resize(n + 1);
        hm[0] = 0;
        for (int i = 1; i <= n; i++){
            hm[i] = (hm[i - 1] * base + f(s[i - 1])) % mod;
        }
    }
    ll get(int l, int r){
        return ((hm[r] - hm[l - 1] * pm[r - l + 1]) % mod + mod) % mod;
    }
};

int main(){
    int t; cin>>t;
    while (t--){
        string s; cin>>s;
        hash_str sol; sol.init(s);
        int i = 1, j = 1, n = (int) s.length(), cnt = 0;;
        while (2 * j <= n){
            if (sol.get(i, j) == sol.get(n - j + 1, n - i + 1)){
                i = j + 1;
                cnt++;
            }
            j++;
        }
        cout<<2 * cnt + (i <= n - i + 1)<<"\n";
    }
}

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