Submission #523627

#	Time	Username	Problem	Language	Result	Execution time	Memory
523627		KoD	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	194 ms	28052 KiB

palindromic

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

using u64 = std::uint64_t;
using u128 = __uint128_t;

constexpr u64 MOD = ((u64)1 << 61) - 1;
constexpr u64 X = 904;

constexpr u64 sum(const u64 x, const u64 y) {
    const u64 z = x + y;
    return z >= MOD ? z - MOD : z;
}

constexpr u64 dif(const u64 x, const u64 y) {
    return x < y ? x + MOD - y : x - y;
}

constexpr u64 prd(const u64 x, const u64 y) {
    const u128 z = (u128)x * (u128)y;
    return sum(z >> 61, z & MOD);
}

void solve() {
    std::string s;
    std::cin >> s;
    const int n = s.size();
    vector<u64> pow(n + 1), hash(n + 1);
    pow[0] = 1;
    for (int i = 0; i < n; ++i) {
        pow[i + 1] = prd(pow[i], X);
        hash[i + 1] = sum(prd(hash[i], X), s[i]);
    }
    const auto fold = [&](const int l, const int r) {
        return dif(hash[r], prd(hash[l], pow[r - l]));
    };
    int l = 0, r = n, ans = 0;
    while (l < r) {
        int len = 1;
        while (fold(l, l + len) != fold(r - len, r)) {
            len += 1;
        }
        l += len;
        r -= len;
        ans += 2;
    }
    std::cout << ans - (l > r) << '\n';
}

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

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