Submission #479260

#	Time	Username	Problem	Language	Result	Execution time	Memory
479260		Rainbowbunny	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	138 ms	13160 KiB

palindromic

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

const int MAXN = 1e6 + 5;
const int mod = 998244353;
const int P = 1823;

int Add(int x, int y, int m = mod)
{
    return x + y >= m ? x + y - m : x + y;
}

int Sub(int x, int y, int m = mod)
{
    return x - y < 0 ? x - y + m : x - y;
}

int Mul(int x, int y, int m = mod)
{  
    return 1ll * x * y % m;
}

int BinPow(int n, int k, int m = mod)
{
    int ans = 1, cur = n;
    while(k)
    {
        if(k & 1)
        {
            ans = Mul(ans, cur);
        }
        cur = Mul(cur, cur);
        k >>= 1;
    }
    return ans;
}

int t;
int pref[MAXN], pw[MAXN], ipw[MAXN];
string s;

int Get(int l, int r)
{
    return Mul(ipw[l], Sub(pref[r], l == 0 ? 0 : pref[l - 1]));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    pw[0] = 1;
    ipw[0] = 1;
    int tmp = BinPow(P, mod - 2);
    for(int i = 1; i < MAXN; i++)
    {
        pw[i] = Mul(pw[i - 1], P);
        ipw[i] = Mul(ipw[i - 1], tmp);
    }
    cin >> t;
    while(t--)
    {
        int ans = 0;
        cin >> s;
        for(int i = 0; i < (int)s.size(); i++)
        {
            pref[i] = (i == 0 ? 0 : pref[i - 1]);
            pref[i] = Add(pref[i], Mul(pw[i], s[i] - 'a' + 1));
        }
        int l = 0, r = s.size() - 1;
        while(l <= r)
        {
            int tmpl = l;
            int tmpr = r;
            while(Get(l, tmpl) != Get(tmpr, r))
            {
                tmpl++;
                tmpr--;
            }
            if(Get(l, tmpl) == Get(tmpr, r))
            {
                if(tmpl < tmpr)
                {
                    ans += 2;
                }
                else
                {
                    ans++;
                }
                tmpl++;
                tmpr--;
            }
            l = tmpl;
            r = tmpr;
        }
        cout << ans << '\n';
    }
}

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