Submission #1148424

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148424		ahmedhali107	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	219 ms	34536 KiB

palindromic

#include <bits/stdc++.h>

#define all(x) begin(x), end(x)

using namespace std;
using ll = long long;

const char nl = '\n';

using ull = unsigned long long;
// do NOT forget to use `init`
// B should be odd
ull B, N;
const ull mod = (1ll << 61) - 1;
vector<ull> pw1, pw2;

inline ull add(ull a, ull b) {
    ull ans = a + b;
    if (ans >= mod) ans -= mod;
    return ans;
}

inline ull mul(ull a, ull b) {
    __int128 ans = __int128{a} * b;
    ans %= mod;
    return ans;
}

void init() {
    pw1.assign(N + 1, 1);
    pw2.assign(N + 1, 1);
    for (int i = 1; i <= N; i++) {
        pw1[i] = mul(B, pw1[i - 1]);
        pw2[i] = B * pw2[i - 1];
    }
}

struct strhash {
    vector<ull> h1, h2;

    strhash(const string &s) {
        h1.assign(s.size(), s[0]);
        h2.assign(s.size(), s[0]);
        for (int i = 1; i < s.size(); i++) {
            h1[i] = add(h1[i - 1], mul(pw1[i], (ull) s[i]));
            h2[i] = h2[i - 1] + pw2[i] * (ull) s[i];
        }
    }

    pair<ull, ull> get(int l, int r) {
        ull ans1 = h1[r], ans2 = h2[r];
        if (l != 0) {
            ans1 = add(ans1, mod - h1[l - 1]);
            ans2 -= h2[l - 1];
        }
        ans1 = mul(ans1, pw1[N - l]);
        ans2 *= pw2[N - l];
        return make_pair(ans1, ans2);
    }
};

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll rand(ll l, ll r) {
    return uniform_int_distribution<ll>(l, r)(rng);
}

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    B = rand(1e3, 1e7), N = s.size();
    if (B % 2 == 0) B++;
    init();
    strhash S(s);
    array<int, 2> l{0, 0}, r{n - 1, n - 1};
    int ans = 0;
    while (l[1] <= r[0]) {
        bool found = false;
        while (l[1] < r[0]) {
            auto [s1, s2] = S.get(l[0], l[1]);
            auto [t1, t2] = S.get(r[0], r[1]);
            if (s1 == t1 && s2 == t2) {
                found = true;
                ans += 2;
                l[0] = l[1] = l[1] + 1;
                r[0] = r[1] = r[0] - 1;
                break;
            }
            l[1]++, r[0]--;
        }
        if (!found) {
            ans++;
            break;
        }
    }
    cout << ans << nl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

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