Submission #229783

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
229783	2020-05-06T12:58:53 Z	tatyam	Palindromes (APIO14_palindrome)	C++17	Compilation error	0 ms	0 KB

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 q(comp, vector<pii>());
    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:57:41: error: class template argument deduction failed:
     priority_queue q(comp, vector<pii>());
                                         ^
palindrome.cpp:57:41: error: no matching function for call to 'priority_queue(main()::<lambda(pii, pii)>&, std::vector<std::pair<int, int> >)'
In file included from /usr/include/c++/7/queue:64:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:86,
                 from palindrome.cpp:1:
/usr/include/c++/7/bits/stl_queue.h:552:2: note: candidate: template<class _Tp, class _Sequence, class _Compare, class _InputIterator> priority_queue(_InputIterator, _InputIterator, const _Compare&, _Sequence&&)-> std::priority_queue<_Tp, _Sequence, _Compare>
  priority_queue(_InputIterator __first, _InputIterator __last,
  ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_queue.h:552:2: note:   template argument deduction/substitution failed:
palindrome.cpp:57:41: note:   deduced conflicting types for parameter '_InputIterator' ('main()::<lambda(pii, pii)>' and 'std::vector<std::pair<int, int> >')
     priority_queue q(comp, vector<pii>());
                                         ^
In file included from /usr/include/c++/7/queue:64:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:86,
                 from palindrome.cpp:1:
/usr/include/c++/7/bits/stl_queue.h:541:2: note: candidate: template<class _Tp, class _Sequence, class _Compare, class _InputIterator> priority_queue(_InputIterator, _InputIterator, const _Compare&, const _Sequence&)-> std::priority_queue<_Tp, _Sequence, _Compare>
  priority_queue(_InputIterator __first, _InputIterator __last,
  ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_queue.h:541:2: note:   template argument deduction/substitution failed:
palindrome.cpp:57:41: note:   deduced conflicting types for parameter '_InputIterator' ('main()::<lambda(pii, pii)>' and 'std::vector<std::pair<int, int> >')
     priority_queue q(comp, vector<pii>());
                                         ^
In file included from /usr/include/c++/7/queue:64:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:86,
                 from palindrome.cpp:1:
/usr/include/c++/7/bits/stl_queue.h:509:2: note: candidate: template<class _Tp, class _Sequence, class _Compare, class _Alloc, class _Requires> priority_queue(std::priority_queue<_Tp, _Sequence, _Compare>&&, const _Alloc&)-> std::priority_queue<_Tp, _Sequence, _Compare>
  priority_queue(priority_queue&& __q, const _Alloc& __a)
  ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_queue.h:509:2: note:   template argument deduction/substitution failed:
palindrome.cpp:57:41: note:   'main()::<lambda(pii, pii)>' is not derived from 'std::priority_queue<_Tp, _Sequence, _Compare>'
     priority_queue q(comp, vector<pii>());
                                         ^
In file included from /usr/include/c++/7/queue:64:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:86,
                 from palindrome.cpp:1:
/usr/include/c++/7/bits/stl_queue.h:505:2: note: candidate: template<class _Tp, class _Sequence, class _Compare, class _Alloc, class _Requires> priority_queue(const std::priority_queue<_Tp, _Sequence, _Compare>&, const _Alloc&)-> std::priority_queue<_Tp, _Sequence, _Compare>
  priority_queue(const priority_queue& __q, const _Alloc& __a)
  ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_queue.h:505:2: note:   template argument deduction/substitution failed:
palindrome.cpp:57:41: note:   'main()::<lambda(pii, pii)>' is not derived from 'const std::priority_queue<_Tp, _Sequence, _Compare>'
     priority_queue q(comp, vector<pii>());
                                         ^
In file included from /usr/include/c++/7/queue:64:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:86,
                 from palindrome.cpp:1:
/usr/include/c++/7/bits/stl_queue.h:501:2: note: candidate: template<class _Tp, class _Sequence, class _Compare, class _Alloc, class _Requires> priority_queue(const _Compare&, _Sequence&&, const _Alloc&)-> std::priority_queue<_Tp, _Sequence, _Compare>
  priority_queue(const _Compare& __x, _Sequence&& __c, const _Alloc& __a)
  ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_queue.h:501:2: note:   template argument deduction/substitution failed:
palindrome.cpp:57:41: note:   candidate expects 3 arguments, 2 provided
     priority_queue q(comp, vector<pii>());
                                         ^
In file included from /usr/include/c++/7/queue:64:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:86,
                 from palindrome.cpp:1:
/usr/include/c++/7/bits/stl_queue.h:496:2: note: candidate: template<class _Tp, class _Sequence, class _Compare, class _Alloc, class _Requires> priority_queue(const _Compare&, const _Sequence&, const _Alloc&)-> std::priority_queue<_Tp, _Sequence, _Compare>
  priority_queue(const _Compare& __x, const _Sequence& __c,
  ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_queue.h:496:2: note:   template argument deduction/substitution failed:
palindrome.cpp:57:41: note:   candidate expects 3 arguments, 2 provided
     priority_queue q(comp, vector<pii>());
                                         ^
In file included from /usr/include/c++/7/queue:64:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:86,
                 from palindrome.cpp:1:
/usr/include/c++/7/bits/stl_queue.h:492:2: note: candidate: template<class _Tp, class _Sequence, class _Compare, class _Alloc, class _Requires> priority_queue(const _Compare&, const _Alloc&)-> std::priority_queue<_Tp, _Sequence, _Compare>
  priority_queue(const _Compare& __x, const _Alloc& __a)
  ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_queue.h:492:2: note:   template argument deduction/substitution failed:
palindrome.cpp:57:41: note:   couldn't deduce template parameter '_Tp'
     priority_queue q(comp, vector<pii>());
                                         ^
In file included from /usr/include/c++/7/queue:64:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:86,
                 from palindrome.cpp:1:
/usr/include/c++/7/bits/stl_queue.h:488:2: note: candidate: template<class _Tp, class _Sequence, class _Compare, class _Alloc, class _Requires> priority_queue(const _Alloc&)-> std::priority_queue<_Tp, _Sequence, _Compare>
  priority_queue(const _Alloc& __a)
  ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_queue.h:488:2: note:   template argument deduction/substitution failed:
palindrome.cpp:57:41: note:   candidate expects 1 argument, 2 provided
     priority_queue q(comp, vector<pii>());
                                         ^
In file included from /usr/include/c++/7/queue:64:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:86,
                 from palindrome.cpp:1:
/usr/include/c++/7/bits/stl_queue.h:482:7: note: candidate: template<class _Tp, class _Sequence, class _Compare> priority_queue(const _Compare&, _Sequence&&)-> std::priority_queue<_Tp, _Sequence, _Compare>
       priority_queue(const _Compare& __x, _Sequence&& __s = _Sequence())
       ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_queue.h:482:7: note:   template argument deduction/substitution failed:
palindrome.cpp:57:41: note:   couldn't deduce template parameter '_Tp'
     priority_queue q(comp, vector<pii>());
                                         ^
In file included from /usr/include/c++/7/queue:64:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:86,
                 from palindrome.cpp:1:
/usr/include/c++/7/bits/stl_queue.h:477:7: note: candidate: template<class _Tp, class _Sequence, class _Compare> priority_queue(const _Compare&, const _Sequence&)-> std::priority_queue<_Tp, _Sequence, _Compare>
       priority_queue(const _Compare& __x, const _Sequence& __s)
       ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_queue.h:477:7: note:   template argument deduction/substitution failed:
palindrome.cpp:57:41: note:   couldn't deduce template parameter '_Tp'
     priority_queue q(comp, vector<pii>());
                                         ^
In file included from /usr/include/c++/7/queue:64:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:86,
                 from palindrome.cpp:1:
/usr/include/c++/7/bits/stl_queue.h:473:2: note: candidate: template<class _Tp, class _Sequence, class _Compare, class _Seq, class _Requires> priority_queue()-> std::priority_queue<_Tp, _Sequence, _Compare>
  priority_queue()
  ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_queue.h:473:2: note:   template argument deduction/substitution failed:
palindrome.cpp:57:41: note:   candidate expects 0 arguments, 2 provided
     priority_queue q(comp, vector<pii>());
                                         ^
palindrome.cpp:59:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < a.size(); i++){
                    ~~^~~~~~~~~~