oj.uz

Submission #229775

# Submission time Handle Problem Language Result Execution time Memory
229775 2020-05-06T10:32:49 Z tatyam Palindromes (APIO14_palindrome) C++17
47 / 100
 240 ms 21968 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, int> 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();
        int 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++){
                    ~~^~~~~~~~~~
palindrome.cpp: In instantiation of 'bool chmax(T&, const U&) [with T = long unsigned int; U = int]':
palindrome.cpp:71:31:   required from here
palindrome.cpp:6:63: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 template<class T, class U> bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; }
                                                             ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 5 ms 256 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 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 256 KB Output is correct
16 Correct 5 ms 256 KB Output is correct
17 Correct 4 ms 256 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 256 KB Output is correct
21 Correct 5 ms 256 KB Output is correct
22 Correct 5 ms 256 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 5 ms 384 KB Output is correct
31 Correct 5 ms 256 KB Output is correct
32 Correct 5 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 5 ms 384 KB Output is correct
11 Correct 5 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 11 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
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 7696 KB Output is correct
2 Correct 76 ms 7436 KB Output is correct
3 Incorrect 78 ms 7948 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 240 ms 21968 KB Output isn't correct
2 Halted 0 ms 0 KB -