Submission #263879

#TimeUsernameProblemLanguageResultExecution timeMemory
263879KoDPalindromes (APIO14_palindrome)C++11
100 / 100
445 ms29212 KiB
/** * @title Template */ #include <iostream> #include <algorithm> #include <utility> #include <numeric> #include <vector> #include <array> #include <cassert> #include <queue> #include <unordered_map> template <class T, class U> bool chmin(T &lhs, const U &rhs) { if (lhs > rhs) { lhs = rhs; return true; } return false; } template <class T, class U> bool chmax(T &lhs, const U &rhs) { if (lhs < rhs) { lhs = rhs; return true; } return false; } /** * @title Chmin/Chmax */ class range { public: class iterator { private: int64_t M_position; public: iterator(int64_t position) noexcept: M_position(position) { } void operator ++ () noexcept { ++M_position; } bool operator != (iterator other) const noexcept { return M_position != other.M_position; } int64_t operator * () const noexcept { return M_position; } }; class reverse_iterator { private: int64_t M_position; public: reverse_iterator(int64_t position) noexcept: M_position(position) { } void operator ++ () noexcept { --M_position; } bool operator != (reverse_iterator other) const noexcept { return M_position != other.M_position; } int64_t operator * () const noexcept { return M_position; } }; private: const iterator M_first, M_last; public: range(int64_t first, int64_t last) noexcept: M_first(first), M_last(std::max(first, last)) { } iterator begin() const noexcept { return M_first; } iterator end() const noexcept { return M_last; } reverse_iterator rbegin() const noexcept { return reverse_iterator(*M_last - 1); } reverse_iterator rend() const noexcept { return reverse_iterator(*M_first - 1); } }; /** * @title Range */ #include <type_traits> #include <iterator> template <class T> class rev_impl { public: using iterator = decltype(std::declval<T>().rbegin()); private: const iterator M_begin; const iterator M_end; public: rev_impl(T &&cont) noexcept: M_begin(cont.rbegin()), M_end(cont.rend()) { } iterator begin() const noexcept { return M_begin; } iterator end() const noexcept { return M_end; } }; template <class T> rev_impl<T> rev(T &&cont) { return rev_impl<T>(std::forward<T>(cont)); } /** * @title Reverser */ #include <cstddef> #include <cstdint> template <class InputIterator> class manacher_impl { public: using value_type = typename InputIterator::value_type; public: std::vector<size_t> odd, even; explicit manacher_impl(InputIterator first, InputIterator last, const value_type &never) { const size_t size = std::distance(first, last); odd.resize(size); even.resize(size - 1); std::vector<value_type> str; str.reserve(2 * size + 1); for (; first != last; ++first) { str.push_back(never); str.push_back(*first); } str.push_back(never); std::vector<int32_t> calc(str.size()); int32_t i = 0, j = 0; while (i < (int32_t) str.size()) { while (i - j >= 0 && i + j < (int32_t) str.size() && str[i - j] == str[i + j]) { ++j; } calc[i] = j; int32_t k = 1; while (i - k >= 0 && k + calc[i - k] < j) { calc[i + k] = calc[i - k]; ++k; } i += k; j -= k; } for (size_t k = 1; k + 1 < str.size(); ++k) { if (k % 2 == 1) { odd[k / 2] = calc[k] - 1; } else { even[k / 2 - 1] = calc[k] - 1; } } } }; template <class InputIterator> manacher_impl<InputIterator> manacher(InputIterator first, InputIterator last, const typename InputIterator::value_type &never) { return manacher_impl<InputIterator>(first, last, never); } /** * @title Manacher */ #include <random> #include <chrono> #include <type_traits> uint64_t engine() { static const auto rotate = [](const uint64_t x, const size_t k) { return (x << k) | (x >> (64 - k)); }; static auto array = [] { uint64_t seed = static_cast<uint64_t>(std::chrono::system_clock::now().time_since_epoch().count()); std::array<uint64_t, 4> res{}; for (size_t index = 0; index < 4; index++) { uint64_t value = (seed += 0x9e3779b97f4a7c15); value = (value ^ (value >> 30)) * 0xbf58476d1ce4e5b9; value = (value ^ (value >> 27)) * 0x94d049bb133111eb; res[index] = value ^ (value >> 31); } return res; }(); const uint64_t result = rotate(array[1] * 5, 7) * 9; const uint64_t old_value = array[1] << 17; array[2] ^= array[0]; array[3] ^= array[1]; array[1] ^= array[2]; array[0] ^= array[3]; array[2] ^= old_value; array[3] = rotate(array[3], 45); return result; } template <class Integer> typename std::enable_if<std::is_integral<Integer>::value, Integer>::type random_number(Integer lower, Integer upper) { static std::default_random_engine gen(engine()); return std::uniform_int_distribution<Integer>(lower, upper)(gen); } template <class Real> typename std::enable_if<!std::is_integral<Real>::value, Real>::type random_number(Real lower, Real upper) { static std::default_random_engine gen(engine()); return std::uniform_real_distribution<Real>(lower, upper)(gen); } /** * @title Random Number */ #include <string> namespace rolling_hash_detail { class hash61_t { public: static uint64_t mod() { return (static_cast<uint64_t>(1) << 61) - 1; } static uint32_t base() { static const uint32_t value = static_cast<uint32_t>(engine()); return value; } static uint64_t add(uint64_t a, uint64_t b) { a += b; if (a >= mod()) a -= mod(); return a; } static uint64_t sub(uint64_t a, uint64_t b) { a += mod() - b; if (a >= mod()) a -= mod(); return a; } static uint64_t mul(uint64_t a, uint64_t b) { uint64_t l1 = (uint32_t) a, h1 = a >> 32, l2 = (uint32_t) b, h2 = b >> 32; uint64_t l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2; uint64_t res = (l & mod()) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1; res = (res & mod()) + (res >> 61); res = (res & mod()) + (res >> 61); return res - 1; } static std::vector<uint64_t> reserve; static uint64_t power(const size_t index) { if (index >= reserve.size()) { size_t cur = reserve.size(); reserve.resize(index + 1); for (; cur <= index; ++cur) { reserve[cur] = mul(reserve[cur - 1], base()); } } return reserve[index]; } }; std::vector<uint64_t> hash61_t::reserve = std::vector<uint64_t>(1, 1); }; class rolling_hash { public: using hash_type = uint64_t; using size_type = size_t; private: using op_t = rolling_hash_detail::hash61_t; std::string M_string; std::vector<hash_type> M_hash; public: rolling_hash() { initialize(); } rolling_hash(const std::string &initial_) { construct(initial_); } void initialize() { clear(); M_string = ""; M_hash.assign(1, 0); } void construct(const std::string &initial_) { initialize(); add_string(initial_); } void add_string(const std::string &str) { size_type cur_size = M_string.size(); size_type next_size = M_string.size() + str.size(); M_string += str; M_hash.resize(next_size + 1); for (size_type i = cur_size; i < next_size; ++i) { M_hash[i + 1] = op_t::add(op_t::mul(M_hash[i], op_t::base()), M_string[i]); } } hash_type hash(size_type l, size_type r) const { return op_t::sub(M_hash[r], op_t::mul(op_t::power(r - l), M_hash[l])); } size_type lcp(size_type l, size_type r) const { size_type ok = 0, ng = std::min(M_string.size() - l, M_string.size() - r) + 1; while (ng - ok > 1) { size_type md = (ok + ng) >> 1; (hash(l, l + md) == hash(r, r + md) ? ok : ng) = md; } return ok; } const std::string &get() const { return M_string; } size_type size() const { return M_string.size(); } bool empty() const { return M_string.empty(); } void clear() { M_string.clear(); M_string.shrink_to_fit(); M_hash.clear(); M_hash.shrink_to_fit(); } }; /** * @title Rolling Hash */ using i32 = int32_t; using i64 = int64_t; using u32 = uint32_t; using u64 = uint64_t; constexpr i32 inf32 = (i32(1) << 30) - 1; constexpr i64 inf64 = (i64(1) << 62) - 1; struct state { i32 l, r; explicit state(i32 l_, i32 r_): l(l_), r(r_) { } bool operator < (const state &rhs) const { return (r - l) < (rhs.r - rhs.l); } }; int main() { std::string S; std::cin >> S; const auto pal = manacher(S.begin(), S.end(), '$'); const auto rh = rolling_hash(S); std::priority_queue<state> que; std::unordered_map<typename rolling_hash::hash_type, i32> count; const auto push = [&](const i32 l, const i32 r, const i32 add) { if (l >= r) { return; } const auto hash = rh.hash(l, r); if (count.count(hash) == 0) { que.emplace(l, r); } count[hash] += add; }; for (auto i: range(0, S.size())) { const i32 l = i - pal.odd[i] / 2; const i32 r = l + pal.odd[i]; push(l, r, 1); } for (auto i: range(0, S.size() - 1)) { const i32 l = i - pal.even[i] / 2 + 1; const i32 r = l + pal.even[i]; push(l, r, 1); } i64 ans = 0; while (!que.empty()) { const auto top = que.top(); que.pop(); const i32 l = top.l; const i32 r = top.r; const i32 cnt = count[rh.hash(l, r)]; chmax(ans, (i64) (r - l) * cnt); push(l + 1, r - 1, cnt); } std::cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...