Submission #971502

#	Time	Username	Problem	Language	Result	Execution time	Memory
971502		kilkuwu	Palindromes (APIO14_palindrome)	C++17	47 / 100	1056 ms	49192 KiB

palindrome

#include <bits/stdc++.h>

#define nl '\n'

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

constexpr int h_deterministic_base = false;
constexpr int h_mod = 1e9 + 123;
constexpr int h_max_value = 1024;
using HashType = std::pair<int, uint64_t>;

int h_random_base(int lb, int rb) {
  assert(rb - lb >= 2);
  int64_t seed = h_deterministic_base ? 1 : std::chrono::high_resolution_clock::now().time_since_epoch().count();
  std::mt19937_64 rng(seed);
  auto uid = std::uniform_int_distribution<long long>(lb + 1, rb - 1);
  int base = uid(rng);
  return base - (base % 2 == 0);
}

int h_base = h_random_base(h_max_value + 1, h_mod - 1);
std::vector<HashType> h_power = {{1, 1}};

void generate_power(int size) {
  while ((int)h_power.size() < size) {
    h_power.emplace_back((int64_t)h_power.back().first * h_base % h_mod,
                         h_power.back().second * h_base);
  }
}

struct PolynomialHash {
  std::vector<HashType> hval;

  PolynomialHash() {}

  // Assumption: 0 < s[1] < h_base
  PolynomialHash(const std::vector<int>& s) { init(s); }

  // Assumption: 0 < s[1] < h_base
  PolynomialHash(const std::string& s) {
    std::vector<int> val(s.size());
    for (int i = 0; i < (int) s.size(); i++) val[i] = s[i];
    init(val);
  }

  // Assuming that s[i] > 0 
  void init(const std::vector<int>& s) {
    hval.resize(s.size() + 1);
    generate_power(hval.size());
    for (int i = 0; i < (int) s.size(); i++) {
      hval[i + 1].first = ((int64_t) hval[i].first * h_base + s[i]) % h_mod;
      hval[i + 1].second = hval[i].second * h_base + s[i];
    }
  }

  // Get hash of range [l, r)
  HashType get(int l, int r) {
    int r1 = ((int64_t)hval[r].first -
              (int64_t)hval[l].first * h_power[r - l].first) %
             h_mod;
    uint64_t r2 = hval[r].second - hval[l].second * h_power[r - l].second;
    return {r1 + (r1 < 0) * h_mod, r2};
  }
};

struct ReversePolynomialHash {
  PolynomialHash polyhash;

  ReversePolynomialHash() {}
  ReversePolynomialHash(const std::string& s) {
    std::vector<int> val(s.size());
    for (int i = 0; i < (int)s.size(); i++) val[i] = s[s.size() - i - 1];
    polyhash.init(val);
  }
  ReversePolynomialHash(std::vector<int> s) {
    std::reverse(s.begin(), s.end());
    polyhash.init(s);
  }

  // Get reverse hash value of range [l, r)
  HashType get(int l, int r) {
    int n = polyhash.hval.size();
    l = n - l - 1, r = n - r - 1;
    std::swap(l, r);
    return polyhash.get(l, r);
  }
};

const int mxN = 3e5 + 1;
std::map<HashType, int> mp[mxN];

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  
  std::string s;
  std::cin >> s;
  int n = s.size();

  PolynomialHash h1(s);
  ReversePolynomialHash h1r(s);

  for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
      auto hf = h1.get(i, j + 1);
      auto hr = h1r.get(i, j + 1);
      if (hf == hr) {
        mp[j - i + 1][hf]++;
      }
    }
  }

  int64_t ans = 0;
  for (int len = 1; len <= n; len++) {
    for (auto [hv, cnt] : mp[len]) {
      ans = std::max(ans, (int64_t) cnt * len);
    }  
  }

  std::cout << ans << nl;
}

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