Submission #229776

#	Time	Username	Problem	Language	Result	Execution time	Memory
229776		tatyam	Palindromes (APIO14_palindrome)	C++17	100 / 100	303 ms	23760 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
using ull = uint64_t;
using u128 = __uint128_t;
using pii = pair<int, int>;
template<class T, class U> bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; }

constexpr ull mod = 0x1fffffffffffffff, base = 257;
struct RollingHash{
    const int n;
    vector<ull> data, power;
    static constexpr ull mul(ull a, ull b){
        u128 c = (u128)a * b;
        ull ans = ull(c >> 61) + ull(c & mod);
        if(ans >= mod) ans -= mod;
        return ans;
    }
    RollingHash(const string& s): n(s.size()), data(n + 1), power(n + 1){
        power[0] = 1;
        data[0] = 1;
        for(int i = 0; i < n; i++){
            power[i + 1] = mul(power[i], base);
            data[i + 1] = mul(data[i], base) + s[i];
            if(data[i + 1] >= mod) data[i + 1] -= mod;
        }
    }
    ull get(int l, int r){
        const ull L = mul(data[l], power[r - l]);
        const ull R = data[r];
        return R - L + (R < L ? mod : 0);
    }
};
vector<int> manacher(const string& S){
    string s = {S[0]};
    for(int i = 1; i < S.size(); i++){
        s += '$';
        s += S[i];
    }
    const int n = s.size();
    vector a(n, 0);
    for(int i = 0, j = 0; i < n; ){
        while(i - j >= 0 && i + j < n && s[i - j] == s[i + j]) j++;
        a[i] = j;
        int k = 1;
        for(; i - k >= 0 && i + k < n && k + a[i - k] < j; k++) a[i + k] = a[i - k];
        i += k;
        j -= k;
    }
    return a;
}
int main(){
    string s;
    cin >> s;
    RollingHash rh(s);
    auto a = manacher(s);
    auto comp = [](pii a, pii b){ return a.second - a.first < b.second - b.first; };
    priority_queue<pii, vector<pii>, decltype(comp)> q(comp);
    unordered_map<ull, ull> cnt;
    for(int i = 0; i < a.size(); i++){
        int l = (i - a[i] + 2) / 2, r = (i + a[i] + 1) / 2;
        if(l >= r) continue;
        auto [iter, changed] = cnt.try_emplace(rh.get(l, r), 0);
        if(changed) q.emplace(l, r);
        iter->second++;
    }
    ull ans = 0;
    while(q.size()){
        auto [l, r] = q.top();
        q.pop();
        ull a = cnt[rh.get(l, r)];
        chmax(ans, a * (r - l));
        l++; r--;
        if(l < r){
            auto [iter, changed] = cnt.try_emplace(rh.get(l, r), 0);
            if(changed) q.emplace(l, r);
            iter->second += a;
        }
    }
    cout << ans << endl;
}

Compilation message (stderr)

palindrome.cpp: In function 'std::vector<int> manacher(const string&)':
palindrome.cpp:35:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < S.size(); i++){
                    ~~^~~~~~~~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:59:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < a.size(); i++){
                    ~~^~~~~~~~~~

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