Submission #318310

#	Time	Username	Problem	Language	Result	Execution time	Memory
318310		Nima_Naderi	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	980 ms	53388 KiB

palindromic

///In the name of GOD
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 1e6 + 10;
const ll MXH = 3;
const vector<ll> Mab = {1448387, 2888387, 8387};
const vector<ll> Mod = {1000000087, (ll)1e9 + 7, (ll)1e9 + 9};
ll q, n;
ll pw[MXH][MXN], Hash[MXH][MXN];
string s;
ll Get(ll b, ll l, ll r){
    return (Hash[b][r] - Hash[b][l - 1] * pw[b][r - l + 1] % Mod[b] + Mod[b]) % Mod[b];
}
bool Check(ll l1, ll r1, ll l2, ll r2){
    bool f = true;
    for(int b = 0; b < MXH; b ++){
        f &= (Get(b, l1, r1) == Get(b, l2, r2));
    }
    return f;
}
void solve(){
    cin >> s, n = s.size();
    s = "$" + s;
    for(int b = 0; b < MXH; b ++)
        for(int i = 1; i <= n; i ++)
            Hash[b][i] = (Hash[b][i - 1] * Mab[b] % Mod[b] + (s[i] - 'a' + 1)) % Mod[b];
    ll l = 1, r = n, ans = 0;
    while(l < r){
        ll nxtl = -1, nxtr = -1;
        for(int len = 1; l + len - 1 < r - len + 1; len ++){
            if(Check(l, l + len - 1, r - len + 1, r)){
                nxtl = l + len, nxtr = r - len;
                break;
            }
        }
        if(nxtl == -1){
            ans ++; break;
        }
        l = nxtl, r = nxtr, ans += 2;
    }
    if(l == r) ans ++;
    cout << ans << '\n';
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    for(int b = 0; b < MXH; b ++){
        pw[b][0] = 1;
        for(int i = 1; i < MXN; i ++)
            pw[b][i] = pw[b][i - 1] * Mab[b] % Mod[b];
    }
    cin >> q;
    while(q --) solve();
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

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