Submission #712990

#	Time	Username	Problem	Language	Result	Execution time	Memory
712990		Johann	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	215 ms	30144 KiB

palindromic

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

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef tuple<int, int, int> tiii;
typedef vector<tiii> vtiii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

const ll MOD = 1e9 + 7;
const ll P = 61687;

vi pot;
vi pref;
void initHashes(string &s)
{
    int n = sz(s);
    pot.assign(n + 10, 1);
    for (int i = 1; i < sz(pot); ++i)
        pot[i] = (pot[i - 1] * P) % MOD;
    pref.assign(n + 1, 0);
    for (int i = n - 1; i >= 0; --i)
        pref[i] = (P * pref[i + 1] + s[i]) % MOD;
}
ll hashString(int l, int r)
{
    assert(l <= r);
    ll h = (pref[l] - pref[r] * pot[r - l]) % MOD;
    return (h + MOD) % MOD;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;
    while (T--)
    {
        string s;
        cin >> s;
        initHashes(s);

        int ans = 0;
        int l0 = 0, r0 = sz(s);
        int l = 0, r = sz(s);

        while (r - l > 1)
        {
            ++l, --r;
            if (hashString(l0, l) == hashString(r, r0))
            {
                ans += 2;
                l0 = l, r0 = r;
            }
        }
        if (r0 - l0 > 0)
            ++ans;
        cout << ans << "\n";
    }

    return 0;
}

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