Submission #971495

#	Time	Username	Problem	Language	Result	Execution time	Memory
971495		kilkuwu	Palindromes (APIO14_palindrome)	C++17	47 / 100	1044 ms	48880 KiB

palindrome

#include <bits/stdc++.h>

#define nl '\n'

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

int random_base(int lb, int rb) {

  bool deterministic = false;

  assert(rb - lb >= 2);
  int64_t seed = deterministic ? 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);
}

using HashType = std::pair<int, uint64_t>;

constexpr int h_mod = 1e9 + 123;
const int h_max_value = 1024;
int h_base = random_base(h_max_value, 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() {}

  // Assuming that s[i] > 0 
  PolynomialHash(const std::string& s) : hval(s.size() + 1) {
    generate_power(s.size() + 1);
    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];
    }

  }

  // Assuming that s[i] > 0 
  PolynomialHash(const std::vector<int>& s) : hval(s.size() + 1) {
    generate_power(s.size() + 1);
    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 {
  std::vector<HashType> hval;

  ReversePolynomialHash() {}

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

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

  // Get reverse hash of range [l, r)
  HashType get(int l, int r) {
    l = hval.size() - l - 1;
    r = hval.size() - r - 1;
    std::swap(l, 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};
  }
};

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