Submission #1176379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176379		alterio	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	202 ms	26704 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()

const int mxn = 1e6 + 10, MOD = 1e9 + 7;

ll expo(ll base, ll pwr) {
    ll ans = 1;
    while (pwr) {
        if (pwr & 1) ans = (ans * base) % MOD;
        base = (base * base) % MOD;
        pwr /= 2;
    }
    return ans;
}

ll prf[mxn], pwr[mxn], inv[mxn];

ll get(int l, int r) {
    ll val = (prf[r] - prf[l - 1] + MOD) % MOD;
    val = (val * inv[l]) % MOD;
    return val; 
}

bool same(int l1, int r1, int l2, int r2) {
    ll p1 = get(l1, r1), p2 = get(l2, r2);
    return p1 == p2;
}

void solve() {
    string s;
    cin >> s;
    s = "." + s;
    int n = s.size();
    memset(prf, 0, sizeof(prf));
    for (int i = 1; i < n; i++) prf[i] = (prf[i - 1] + (s[i] - 'a') * pwr[i]) % MOD;
    int last = 1, ans = 0;
    for (int i = 1; i < n; i++) {
        int len = i - last;
        int pos = n - i;
        if (last > pos) break;
        if (same(last, i, pos, pos + len)) {
            ans += 1 + (last != pos);
            last = i + 1;
        }
    }
    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    pwr[0] = 1;
    for (int i = 1; i < mxn; i++) pwr[i] = (pwr[i - 1] * 26) % MOD; 
    for (int i = 0; i < mxn; i++) inv[i] = expo(pwr[i], MOD - 2);
    int t;
    cin >> t;
    while (t--) solve();
}

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