#line 1 "main.cpp"
/**
* @title Template
*/
#include <iostream>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>
#include <cassert>
#include <map>
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/chmin_chmax.cpp"
template <class T, class U>
constexpr bool chmin(T &lhs, const U &rhs) {
if (lhs > rhs) {
lhs = rhs;
return true;
}
return false;
}
template <class T, class U>
constexpr bool chmax(T &lhs, const U &rhs) {
if (lhs < rhs) {
lhs = rhs;
return true;
}
return false;
}
/**
* @title Chmin/Chmax
*/
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/range.cpp"
#line 4 "/Users/kodamankod/Desktop/Programming/Library/other/range.cpp"
class range {
public:
class iterator {
private:
int64_t M_position;
public:
constexpr iterator(int64_t position) noexcept: M_position(position) { }
constexpr void operator ++ () noexcept { ++M_position; }
constexpr bool operator != (iterator other) const noexcept { return M_position != other.M_position; }
constexpr int64_t operator * () const noexcept { return M_position; }
};
class reverse_iterator {
private:
int64_t M_position;
public:
constexpr reverse_iterator(int64_t position) noexcept: M_position(position) { }
constexpr void operator ++ () noexcept { --M_position; }
constexpr bool operator != (reverse_iterator other) const noexcept { return M_position != other.M_position; }
constexpr int64_t operator * () const noexcept { return M_position; }
};
private:
const iterator M_first, M_last;
public:
constexpr range(int64_t first, int64_t last) noexcept: M_first(first), M_last(std::max(first, last)) { }
constexpr iterator begin() const noexcept { return M_first; }
constexpr iterator end() const noexcept { return M_last; }
constexpr reverse_iterator rbegin() const noexcept { return reverse_iterator(*M_last - 1); }
constexpr reverse_iterator rend() const noexcept { return reverse_iterator(*M_first - 1); }
};
/**
* @title Range
*/
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/rev.cpp"
#include <type_traits>
#include <iterator>
#line 6 "/Users/kodamankod/Desktop/Programming/Library/other/rev.cpp"
template <class T>
class rev_impl {
public:
using iterator = typename std::decay<T>::type::reverse_iterator;
private:
const iterator M_begin;
const iterator M_end;
public:
constexpr rev_impl(T &&cont) noexcept: M_begin(std::rbegin(cont)), M_end(std::rend(cont)) { }
constexpr iterator begin() const noexcept { return M_begin; }
constexpr iterator end() const noexcept { return M_end; }
};
template <class T>
constexpr decltype(auto) rev(T &&cont) {
return rev_impl<T>(std::forward<T>(cont));
}
/**
* @title Reverser
*/
#line 2 "/Users/kodamankod/Desktop/Programming/Library/string/rolling_hash.cpp"
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/random_number.cpp"
#include <cstdint>
#include <random>
#include <chrono>
#line 7 "/Users/kodamankod/Desktop/Programming/Library/other/random_number.cpp"
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>
Integer random_integer(Integer lower, Integer upper) {
static std::default_random_engine gen(engine());
return std::uniform_int_distribution<Integer>(lower, upper)(gen);
}
template <class Real>
Real random_real(Real lower, Real upper) {
static std::default_random_engine gen(engine());
return std::uniform_real_distribution<Real>(lower, upper)(gen);
}
/**
* @title Random Number
*/
#line 4 "/Users/kodamankod/Desktop/Programming/Library/string/rolling_hash.cpp"
#include <cstddef>
#line 7 "/Users/kodamankod/Desktop/Programming/Library/string/rolling_hash.cpp"
#include <string>
#line 9 "/Users/kodamankod/Desktop/Programming/Library/string/rolling_hash.cpp"
class rolling_hash {
public:
using mod_type = uint64_t;
using base_type = uint32_t;
using size_type = size_t;
private:
std::string M_string;
std::vector<mod_type> M_power, M_hash;
static constexpr mod_type S_mod = (mod_type(1) << 61) - 1;
static base_type S_base() {
static const base_type value = engine();
return value;
}
public:
rolling_hash() { initialize(); }
rolling_hash(const std::string &initial_) { construct(initial_); }
void initialize() {
clear();
M_string = "";
M_power.assign(1, 1);
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_power.resize(next_size + 1);
M_hash.resize(next_size + 1);
for (size_type i = cur_size; i < next_size; ++i) {
M_power[i + 1] = (__uint128_t) M_power[i] * S_base() % S_mod;
M_hash[i + 1] = ((__uint128_t) M_hash[i] * S_base() + M_string[i]) % S_mod;
}
}
mod_type hash(size_type l, size_type r) const {
return (M_hash[r] + S_mod - ((__uint128_t) M_power[r - l] * M_hash[l]) % S_mod) % S_mod;
}
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_power.clear();
M_power.shrink_to_fit();
M_hash.clear();
M_hash.shrink_to_fit();
}
};
/**
* @title Rolling Hash
*/
#line 19 "main.cpp"
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;
int main() {
std::string S;
std::cin >> S;
i32 N = S.size();
assert(N <= 10000);
rolling_hash rh(S), revrh(std::string(S.rbegin(), S.rend()));
auto palindrome = [&](i32 l, i32 r) {
return rh.hash(l, r) == revrh.hash(N - r, N - l);
};
std::map<rolling_hash::mod_type, i32> count;
for (auto l: range(0, N)) {
for (auto r: range(l + 1, N + 1)) {
count[rh.hash(l, r)]++;
}
}
i32 ans = 0;
for (auto l: range(0, N)) {
for (auto r: range(l + 1, N + 1)) {
if (palindrome(l, r)) {
chmax(ans, (r - l) * count[rh.hash(l, r)]);
}
}
std::cout << '\n';
}
std::cout << ans << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
0 ms |
256 KB |
Output is correct |
| 3 |
Correct |
0 ms |
256 KB |
Output is correct |
| 4 |
Correct |
1 ms |
256 KB |
Output is correct |
| 5 |
Correct |
0 ms |
256 KB |
Output is correct |
| 6 |
Correct |
1 ms |
256 KB |
Output is correct |
| 7 |
Correct |
0 ms |
256 KB |
Output is correct |
| 8 |
Correct |
0 ms |
256 KB |
Output is correct |
| 9 |
Correct |
0 ms |
256 KB |
Output is correct |
| 10 |
Correct |
0 ms |
256 KB |
Output is correct |
| 11 |
Correct |
0 ms |
384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
256 KB |
Output is correct |
| 13 |
Correct |
0 ms |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
384 KB |
Output is correct |
| 15 |
Correct |
1 ms |
384 KB |
Output is correct |
| 16 |
Correct |
0 ms |
384 KB |
Output is correct |
| 17 |
Correct |
1 ms |
384 KB |
Output is correct |
| 18 |
Correct |
0 ms |
384 KB |
Output is correct |
| 19 |
Correct |
1 ms |
384 KB |
Output is correct |
| 20 |
Correct |
1 ms |
384 KB |
Output is correct |
| 21 |
Correct |
2 ms |
512 KB |
Output is correct |
| 22 |
Correct |
2 ms |
640 KB |
Output is correct |
| 23 |
Correct |
1 ms |
384 KB |
Output is correct |
| 24 |
Correct |
1 ms |
512 KB |
Output is correct |
| 25 |
Correct |
1 ms |
256 KB |
Output is correct |
| 26 |
Correct |
2 ms |
512 KB |
Output is correct |
| 27 |
Correct |
2 ms |
512 KB |
Output is correct |
| 28 |
Correct |
2 ms |
512 KB |
Output is correct |
| 29 |
Correct |
2 ms |
640 KB |
Output is correct |
| 30 |
Correct |
2 ms |
640 KB |
Output is correct |
| 31 |
Correct |
2 ms |
640 KB |
Output is correct |
| 32 |
Correct |
2 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
512 KB |
Output is correct |
| 2 |
Correct |
344 ms |
17016 KB |
Output is correct |
| 3 |
Correct |
81 ms |
384 KB |
Output is correct |
| 4 |
Correct |
496 ms |
28152 KB |
Output is correct |
| 5 |
Correct |
81 ms |
384 KB |
Output is correct |
| 6 |
Correct |
78 ms |
384 KB |
Output is correct |
| 7 |
Correct |
430 ms |
21368 KB |
Output is correct |
| 8 |
Correct |
82 ms |
512 KB |
Output is correct |
| 9 |
Correct |
562 ms |
29160 KB |
Output is correct |
| 10 |
Correct |
548 ms |
31352 KB |
Output is correct |
| 11 |
Correct |
585 ms |
31352 KB |
Output is correct |
| 12 |
Correct |
506 ms |
24188 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1094 ms |
1920 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
1024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
1692 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
