oj.uz

Submission #229776

# Submission time Handle Problem Language Result Execution time Memory
229776 2020-05-06T10:35:03 Z tatyam Palindromes (APIO14_palindrome) C++17
100 / 100
 303 ms 23760 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 4 ms 256 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 256 KB Output is correct
10 Correct 5 ms 256 KB Output is correct
11 Correct 4 ms 256 KB Output is correct
12 Correct 5 ms 256 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 5 ms 256 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 4 ms 256 KB Output is correct
20 Correct 4 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 256 KB Output is correct
23 Correct 4 ms 256 KB Output is correct
24 Correct 4 ms 256 KB Output is correct
25 Correct 4 ms 256 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 5 ms 256 KB Output is correct
28 Correct 4 ms 256 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 4 ms 256 KB Output is correct
31 Correct 4 ms 256 KB Output is correct
32 Correct 4 ms 256 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1152 KB Output is correct
2 Correct 10 ms 1024 KB Output is correct
3 Correct 9 ms 1024 KB Output is correct
4 Correct 10 ms 1024 KB Output is correct
5 Correct 8 ms 1024 KB Output is correct
6 Correct 9 ms 1024 KB Output is correct
7 Correct 9 ms 1024 KB Output is correct
8 Correct 6 ms 640 KB Output is correct
9 Correct 6 ms 640 KB Output is correct
10 Correct 7 ms 896 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 7692 KB Output is correct
2 Correct 61 ms 7440 KB Output is correct
3 Correct 65 ms 7564 KB Output is correct
4 Correct 75 ms 7696 KB Output is correct
5 Correct 43 ms 6808 KB Output is correct
6 Correct 46 ms 6164 KB Output is correct
7 Correct 59 ms 6928 KB Output is correct
8 Correct 18 ms 3328 KB Output is correct
9 Correct 27 ms 4028 KB Output is correct
10 Correct 40 ms 6420 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 21708 KB Output is correct
2 Correct 262 ms 22352 KB Output is correct
3 Correct 303 ms 23760 KB Output is correct
4 Correct 279 ms 23760 KB Output is correct
5 Correct 169 ms 20948 KB Output is correct
6 Correct 231 ms 21504 KB Output is correct
7 Correct 234 ms 21352 KB Output is correct
8 Correct 42 ms 8664 KB Output is correct
9 Correct 42 ms 8656 KB Output is correct
10 Correct 149 ms 19972 KB Output is correct
11 Correct 236 ms 21204 KB Output is correct
12 Correct 56 ms 9600 KB Output is correct