Submission #666758

#	Time	Username	Problem	Language	Result	Execution time	Memory
666758		ParsaS	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	137 ms	24796 KiB

palindromic

// In the name  f God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 1e6 + 5, MOD = 1e9 + 7, P = 101;
int n, pw[N], hsh[N], inv[N];
string s;

int get_hsh(int l, int r) {
    //cout << hsh[r] << ' ' << hsh[l - 1] << endl;
    return 1LL * (hsh[r] - hsh[l - 1] + MOD) % MOD * inv[l - 1] % MOD;
}
int binpow(int a, int b) {
    return b ? 1LL * binpow(1LL * a * a % MOD, b / 2) * (b % 2 ? a : 1) % MOD : 1;
}
void solve() {
    cin >> s;
    n = s.size();
    s = '.' + s;
    for (int i = 1; i <= n; i++) {
        hsh[i] = (hsh[i - 1] + 1LL * (s[i] - 'a' + 1) * pw[i] % MOD) % MOD;
    }
    int l = 1, r = n, ans = 0;
    while (l <= r) {
        int lp = l, rp = r;
        while (l <= r && get_hsh(lp, l) != get_hsh(r, rp))
            l++, r--;
        if (l >= r) {
            ans++;
            break;
        }
        ans += 2;
        l++, r--;
    }
    cout << ans << '\n';
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    pw[0] = 1;
    for (int i = 1; i < N; i++)
        pw[i] = 1LL * P * pw[i - 1] % MOD;
    inv[N - 1] = binpow(pw[N - 1], MOD - 2);
    for (int i = N - 2; i >= 0; i--)
        inv[i] = 1LL * inv[i + 1] * P % MOD;
    int tc = 1; cin >> tc;
    while (tc--) {
        solve();
    }
    return 0;
}

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