Submission #375874

#	Time	Username	Problem	Language	Result	Execution time	Memory
375874		KoD	Palindromes (APIO14_palindrome)	C++17	100 / 100	624 ms	53792 KiB

palindrome

#include <bits/extc++.h>

using ll = long long;

template <class T>
using Vec = std::vector<T>;

template <class T, class U>
using HashTable = __gnu_pbds::gp_hash_table<T, U>;

ll rand_ll(const ll low, const ll high) {
    static std::random_device dev;
    static std::default_random_engine gen(dev() ^ std::clock());
    return std::uniform_int_distribution<ll>(low, high)(gen);
}

constexpr ll MOD = (1ll << 61) - 1;
const ll BASE = rand_ll(0, MOD - 1);

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

constexpr ll prod(const ll x, const ll y) {
    return ((__int128_t) x * y) % MOD;
}


struct RollingHash {
    Vec<ll> pow, dp;
    RollingHash(const std::string &str) {
        const int size = (int) str.size();
        pow.resize(size + 1);
        dp.resize(size + 1);
        pow[0] = 1;
        dp[1] = 0;
        for (int i = 0; i < size; ++i) {
            pow[i + 1] = prod(pow[i], BASE);
            dp[i + 1] = sum(prod(dp[i], BASE), (ll) str[i]);
        }
    }
    ll hash(const int l, const int r) const {
        return sum(dp[r], MOD - prod(dp[l], pow[r - l]));
    }
};


struct Range {
    int l, r;
    Range(const int l, const int r): l(l), r(r) { }
    bool operator < (const Range &other) const {
        return r - l < other.r - other.l;
    }
};

int main() {
    std::string S;
    std::cin >> S;
    const int N = (int) S.size();
    RollingHash rh(S);
    RollingHash rh_rev(std::string(S.rbegin(), S.rend()));
    const auto is_palindrome = [&](const int l, const int r) {
        if (l < 0 || r > N) {
            return false;
        }
        return rh.hash(l, r) == rh_rev.hash(N - r, N - l);
    };
    std::priority_queue<Range> heap;
    HashTable<ll, int> count;
    const auto add = [&](const int l, const int r, const int x) {
        const auto hash = rh.hash(l, r);
        if (count[hash] == 0) {
            heap.emplace(l, r);
        }
        count[hash] += x;
    };
    for (int i = 0; i < N; ++i) {
        int ok = 0, ng = N + 1;
        while (ng - ok > 1) {
            const auto md = (ok + ng) / 2;
            if (is_palindrome(i - md, i + md + 1)) {
                ok = md;
            }   
            else {
                ng = md;
            }
        }
        add(i - ok, i + ok + 1, 1);
    }   
    for (int i = 1; i < N; ++i) {
        if (S[i - 1] != S[i]) {
            continue;
        }
        int ok = 1, ng = N + 1;
        while (ng - ok > 1) {
            const auto md = (ok + ng) / 2;
            if (is_palindrome(i - md, i + md)) {
                ok = md;
            }   
            else {
                ng = md;
            }
        }
        add(i - ok, i + ok, 1);
    }
    ll ans = 0;
    while (!heap.empty()) {
        const auto [l, r] = heap.top();
        heap.pop();
        const auto c = count[rh.hash(l, r)];
        ans = std::max(ans, (ll) c * (r - l));
        if (r - l > 2) {
            add(l + 1, r - 1, c);
        }
    }
    std::cout << ans << '\n';
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27