Submission #1282551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282551		Peti4	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	285 ms	26772 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;

//#define int long long

#define ll long long
#define all(v) v.begin(), v.end()
#define vi vector<int>
#define el '\n'
#define pii pair<int, int>

const int N = 1e6 + 2;

const int Hnum = 2;
#define pt4 array<int, Hnum>

pt4 mods, bases, pw[N];

bool is_prime(int n)
{
    if (n <= 1) return 0;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return 0;
    return 1;
}

void pre()
{
    random_device rd;
    mt19937 mt(rd());
    auto rnd = [&] (int l, int r) {return uniform_int_distribution<int>(l, r)(mt);};
    for (int i = 0; i < Hnum; i++) bases[i] = rnd(100, 500);
    for (int i = 0; i < Hnum; i++)
    {
        mods[i] = rnd(2e8, 2e9);
        while (!is_prime(mods[i])) --mods[i];
    }
    for (int i = 0; i < Hnum; i++) pw[0][i] = 1;
    for (int i = 1; i < N; i++)
        for (int j = 0; j < Hnum; j++) pw[i][j] = pw[i-1][j] * 1ll * bases[j] % mods[j];
}


struct Hash
{
    vector<pt4> prefix, suffix;
    int n;
    Hash(string &s)
    {
        n = s.size();
        init_prefix(s);
        init_suffix(s);
    }
    void init_prefix(string &s)
    {
        prefix.assign(n, {});
        pt4 pr{};
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < Hnum; j++)
            {
                pr[j] = (pr[j] * 1ll * bases[j] + s[i]) % mods[j];
            }
            prefix[i] = pr;
        }
    }
    void init_suffix(string &s)
    {
        suffix.assign(n, {});
        pt4 pr{};
        for (int i = n-1; i >= 0; i--)
        {
            for (int j = 0; j < Hnum; j++)
            {
                pr[j] = (pr[j] * 1ll * bases[j] + s[i]) % mods[j];
            }
            suffix[i] = pr;
        }
    }
    pt4 get(int l, int r)
    {
        if (!l) return prefix[r];
        pt4 ret = prefix[r];
        for (int i = 0; i < Hnum; i++)
        {
            ret[i] -= (prefix[l-1][i] * 1ll * pw[r-l+1][i]) % mods[i];
            if (ret[i] < 0) ret[i] += mods[i];
        }
        return ret;
    }
    pt4 getr(int l, int r)
    {
        if (r == n-1) return suffix[l];
        pt4 ret = suffix[l];
        for (int i = 0; i < Hnum; i++)
        {
            ret[i] -= (suffix[r+1][i] * 1ll * pw[r-l+1][i]) % mods[i];
            if (ret[i] < 0) ret[i] += mods[i];
        }
        return ret;
    }
};

void solve()
{
    string s; cin >> s;
    Hash h(s);
    int n = s.size(), l = 0, r = n-1, ans = 0, tmp = 0;
    while (2*(l+tmp)+1 < n)
    {
        if (h.get(l, l+tmp) == h.get(r-tmp, r))
        {
            ans += 2;
            l += tmp+1;
            r -= (tmp+1);
            tmp = 0;
        }
        else  tmp++;
    }
    if (2*l != n) ans++;
    cout << ans << el;

}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
pre();
    int t = 1;
    cin >> t;
    while (t--) {solve();}
}

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