Submission #1170652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170652		chikien2009	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	200 ms	34572 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

const long long mod = 1e9 + 9, base = 29;
long long powmod[1000001], invmod[1000001];

inline long long Bpow(long long inp, long long ind)
{
    long long res = 1;
    do
    {
        if (ind & 1)
        {
            res = (res * inp) % mod;
        }
        inp = (inp * inp) % mod;
    } while (ind >>= 1);
    return res;
}

inline void PreCalculate()
{
    powmod[0] = 1;
    invmod[0] = Bpow(powmod[0], mod - 2);
    for (int i = 1; i <= 1e6; ++i)
    {
        powmod[i] = (powmod[i - 1] * base) % mod;
        invmod[i] = Bpow(powmod[i], mod - 2);
    }
}

class HASH_STRING
{
    private:
    vector<long long> pre;
    public:
    inline void Init(string inp)
    {
        pre.clear();
        pre.resize(inp.size() + 1, 0);
        inp = '#' + inp;
        for (int i = 1; i < inp.size(); ++i)
        {
            pre[i] = (pre[i - 1] + powmod[i] * (inp[i] - 'a' + 1)) % mod;
        }
    }
    inline long long GetHash(int l, int r)
    {
        return ((pre[r] - pre[l - 1]) * invmod[l] + mod * mod) % mod;
    }
};

int t, res;
string s;
HASH_STRING hash_s;

int main()
{
    setup();

    PreCalculate();
    cin >> t;
    while (t--)
    {
        cin >> s;
        res = 0;
        hash_s.Init(s);
        for (int i = 1, j = s.size(); i <= j;)
        {
            for (int k = 0; k <= j - i; ++k)
            {
                if (hash_s.GetHash(i, i + k) == hash_s.GetHash(j - k, j))
                {
                    res += 1 + (j - i != k);
                    i += k + 1;
                    j -= k + 1;
                    break;
                }
            }
        }
        cout << res << "\n";
    }
    return 0;
}

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