Submission #588652

#	Time	Username	Problem	Language	Result	Execution time	Memory
588652		bebra	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	354 ms	43204 KiB

palindromic

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

#define dbg(x) cerr << #x << ": " << x << endl;


template<long long Base, long long Mod>
struct Hash {
    static const long long BASE = Base;
    static const long long MOD = Mod;

    vector<long long> pref;
    vector<long long> powers;
    int size;

    Hash() {}
    Hash(const string& s) {
        int n = s.size() + 1;
        pref.resize(n);
        powers.assign(n, 1);
        for (int i = 1; i < n; ++i) {
            int c = s[i - 1] - 'a' + 1;
            pref[i] = (pref[i - 1] * BASE + c) % MOD;
            powers[i] = (powers[i - 1] * BASE) % MOD;
        }
    }

    long long substr(int l, int r) const {
        ++l, ++r;
        long long result = (pref[r] - pref[l - 1] * powers[r - l + 1]) % MOD;
        if (result < 0) result += MOD;
        return result;
    }
};

struct DoubleHash {
    using hash_t1 = Hash<310073, 1084719133>;
    using hash_t2 = Hash<513101, 1259117633>;
    hash_t1 h1;
    hash_t2 h2;
    DoubleHash(const string& s) {
        h1 = s;
        h2 = s;
    }
    pair<long long, long long> substr(int l, int r) const {
        return {h1.substr(l, r), h2.substr(l, r)};
    }
};


void solve() {
    string s;
    cin >> s;
    int n = s.size();
    DoubleHash h(s);
    int ans = 0;
    int prev_i = 0;
    int i = 0;
    int prev_j = n - 1;
    int j = n - 1;
    vector<bool> used(n);
    while (i < j) {
        if (h.substr(prev_i, i) == h.substr(j, prev_j)) {
            for (int k = prev_i; k <= i; ++k) {
                used[k] = true;
            }
            for (int k = j; k <= prev_j; ++k) {
                used[k] = true;
            }
            ans += 2;
            ++i;
            prev_i = i;
            --j;
            prev_j = j;
        } else {
            ++i;
            --j;
        }
    }
    for (int k = 0; k < n; ++k) {
        if (!used[k]) {
            ++ans;
            break;
        }
    }
    cout << ans << '\n';
}


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

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