Submission #924937

#	Time	Username	Problem	Language	Result	Execution time	Memory
924937		sleepntsheep	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	1937 ms	58728 KiB

palindromic

#include <bits/stdc++.h>

#define N 200005
#define ALL(x) begin(x), end(x)
using namespace std;

#define int long long

constexpr long long B { 31 }, M { 1000000007 };


int docase()
{
    string s;
    cin >> s;
    int n = s.size(), z {};
    s = "0" + s;
    vector<int> h(2*n+2, 0), pw(2*n+2, 1), ipw(2*n+2, 1);

    auto bpow = [&](auto &&bpow, long long a, long long b) -> long long {
        if (!b) return 1;
        auto r = bpow(bpow, a, b>>1);
        if (b&1) return r*r%M*a%M;
        return r*r%M;
    };

    for (auto &c : s) c -= 'a';

    for (int i = 1; i <= n; ++i)
        pw[i] = 1ll * pw[i-1] * B % M, ipw[i] = bpow(bpow, pw[i], M-2);

    for (int i = 1; i <= n; ++i)
        h[i] = (h[i-1] + ((long long)s[i] * pw[i] % M)) % M;


    auto sub = [&](int l, int r){
        auto base = (h[r] - h[l-1] + M) % M;
        (base *= ipw[l]) %= M;
        return base;
    };

    for (int l, i = 1, j = n; i <= j;)
    {
        l = 1;
        while (i+l-1 <= j and sub(i, i+l-1) != sub(j-l+1, j)) ++l;
        if (i+l-1 >= j){++z; break;}
        i+=l,j-=l,++z,++z;
    }

    cout << z << '\n';

    return 0;
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int T;
    cin >> T;
    while (T--) docase();
    return 0;
}

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