Submission #678714

#	Time	Username	Problem	Language	Result	Execution time	Memory
678714		stevancv	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	243 ms	24688 KiB

palindromic

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e6 + 2;
const int mod = 1e9 + 7;
int Add(int a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    return a;
}
int Sub(int a, int b) {
    a -= b;
    if (a < 0) a += mod;
    return a;
}
int Mul(int a, int b) {
    ll c = a; c *= b; c %= mod;
    return c;
}
int Exp(int a, int b) {
    int ans = 1;
    while (b > 0) {
        if (b & 1) ans = Mul(ans, a);
        a = Mul(a, a);
        b >>= 1;
    }
    return ans;
}
int p[N], pw[N], inv[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    pw[0] = inv[0] = 1;
    for (int i = 1; i < N; i++) {
        pw[i] = Mul(pw[i - 1], 26);
        inv[i] = Exp(pw[i], mod - 2);
    }
    int tt; cin >> tt;
    while (tt--) {
        string s; cin >> s;
        int n = s.size();
        for (int i = 0; i < n; i++) {
            p[i] = Mul(pw[i], s[i] - 'a');
            if (i > 0) p[i] = Add(p[i - 1], p[i]);
        }
        auto Get = [&] (int l, int r) {
            if (l == 0) return p[r];
            return Mul(inv[l], Sub(p[r], p[l - 1]));
        };
        int l = 0, r = n - 1, ans = 0;
        while (l <= r) {
            if (l == r) {
                ans += 1;
                break;
            }
            int f = 0;
            for (int d = 1; 2 * d < r - l + 2; d++) {
                if (Get(l, l + d - 1) == Get(r - d + 1, r)) {
                    ans += 2;
                    l = l + d;
                    r = r - d;
                    f = 1;
                    break;
                }
            }
            if (f == 0) {
                ans += 1;
                break;
            }
        }
        cout << ans << en;
    }
    return 0;
}

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