Submission #260313

#	Time	Username	Problem	Language	Result	Execution time	Memory
260313		KoD	Palindromes (APIO14_palindrome)	C++11	23 / 100	491 ms	31352 KiB

palindrome

#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/APIO2020/Library/other/chmin_chmax.cpp"

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
 */
#line 2 "/Users/kodamankod/Desktop/APIO2020/Library/other/range.cpp"

#line 4 "/Users/kodamankod/Desktop/APIO2020/Library/other/range.cpp"

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
 */
#line 2 "/Users/kodamankod/Desktop/APIO2020/Library/other/rev.cpp"

#include <type_traits>
#include <iterator>
#line 6 "/Users/kodamankod/Desktop/APIO2020/Library/other/rev.cpp"

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
 */
#line 2 "/Users/kodamankod/Desktop/APIO2020/Library/string/rolling_hash.cpp"

#line 2 "/Users/kodamankod/Desktop/APIO2020/Library/other/random_number.cpp"

#include <cstdint>
#include <random>
#include <chrono>
#line 7 "/Users/kodamankod/Desktop/APIO2020/Library/other/random_number.cpp"
#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
 */
#line 4 "/Users/kodamankod/Desktop/APIO2020/Library/string/rolling_hash.cpp"

#include <cstddef>
#line 8 "/Users/kodamankod/Desktop/APIO2020/Library/string/rolling_hash.cpp"
#include <string>
#line 10 "/Users/kodamankod/Desktop/APIO2020/Library/string/rolling_hash.cpp"

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
 */
#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 <= 1000);
  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::hash_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 << ans << '\n';
  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27