Submission #40120

#	Time	Username	Problem	Language	Result	Execution time	Memory
40120		toonewbie	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	1340 ms	13852 KiB

palindromic

#include <bits/stdc++.h>
 
#define intt long long
#define all(v) (v).begin(),v.end()
 
const intt maxx = 1000006;
const intt MOD = 1000000009;
using namespace std;
 
intt powmod (intt a, intt b, intt mod) {
    intt res = 1;
    a %= mod;
    while (b) {
        if (b & 1)
            res *= a;
        res %= mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
 
intt h[maxx];
int main() {
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    /*
    string a = "bonobo";
    intt t = 31;
    for (intt i = 0; i < a.size(); i++)
        h[i] = (h[i - 1] + t * (a[i] - 'a')) % MOD, t = (t * 31) % MOD;
    cout << (h[1] * powmod (31, 1, MOD) % MOD) << " " << (h[5] - h[3]) * powmod (31, 5, MOD) % MOD << endl;
    */
    //freopen ("in.txt", "r", stdin);
    /*
    string s = "bonobo";
    intt n = s.size(), t = 31;
    for (intt i = 0; i < n; i++)
        h[i] = (h[i - 1] + t * (s[i] - 'a')) % MOD, t = (t * 31) % MOD;
    for (intt i = 0; i < n; i++)
        cout << h[i] << " ";
    cout << endl;
    return 0;
    */
    intt T;
    cin >> T;
    while (T --) {
        memset (h, 0, sizeof (h));
        string s;
        cin >> s;
        intt n = s.size(), t = 31;
        for (intt i = 0; i < n; i++)
            h[i] = (h[i - 1] + t * (s[i] - 'a')) % MOD, t = (t * 31) % MOD;
        intt ll = 0, lr = n - 1, ans = 0;
        for (intt l = 0, r = n - 1; l < r && 0 < r; l ++, r --) {
            intt h1 = (h[l] - h[ll - 1] + MOD + MOD + MOD) * powmod (31, r, MOD);
            h1 %= MOD;
            intt h2 = (h[lr] - h[r - 1] + MOD + MOD + MOD) * powmod (31, ll, MOD);
            h2 %= MOD;
            if (h1 == h2) {
                //cout << ll << " " << lr << endl;
                ans += 2, ll = l + 1, lr = r - 1;
            }
        }
        cout << ans + 1 - (ll > lr) << endl;
        //break;
    }
    return 0;
}

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