oj.uz

Submission #971502

# Submission time Handle Problem Language Result Execution time Memory
971502 2024-04-28T16:56:38 Z kilkuwu Palindromes (APIO14_palindrome) C++17
47 / 100
 1000 ms 49192 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14424 KB Output is correct
2 Correct 4 ms 14428 KB Output is correct
3 Correct 3 ms 14428 KB Output is correct
4 Correct 3 ms 14424 KB Output is correct
5 Correct 3 ms 14428 KB Output is correct
6 Correct 3 ms 14428 KB Output is correct
7 Correct 3 ms 14428 KB Output is correct
8 Correct 3 ms 14424 KB Output is correct
9 Correct 4 ms 14424 KB Output is correct
10 Correct 5 ms 14428 KB Output is correct
11 Correct 4 ms 14428 KB Output is correct
12 Correct 4 ms 14428 KB Output is correct
13 Correct 4 ms 14428 KB Output is correct
14 Correct 3 ms 14424 KB Output is correct
15 Correct 4 ms 14428 KB Output is correct
16 Correct 5 ms 14428 KB Output is correct
17 Correct 3 ms 14428 KB Output is correct
18 Correct 3 ms 14428 KB Output is correct
19 Correct 4 ms 14428 KB Output is correct
20 Correct 4 ms 14428 KB Output is correct
21 Correct 3 ms 14428 KB Output is correct
22 Correct 5 ms 14684 KB Output is correct
23 Correct 5 ms 14428 KB Output is correct
24 Correct 4 ms 14468 KB Output is correct
25 Correct 4 ms 14680 KB Output is correct
26 Correct 4 ms 14428 KB Output is correct
27 Correct 3 ms 14428 KB Output is correct
28 Correct 3 ms 14428 KB Output is correct
29 Correct 3 ms 14424 KB Output is correct
30 Correct 3 ms 14424 KB Output is correct
31 Correct 4 ms 14428 KB Output is correct
32 Correct 4 ms 14440 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14428 KB Output is correct
2 Correct 9 ms 14448 KB Output is correct
3 Correct 12 ms 14428 KB Output is correct
4 Correct 8 ms 14428 KB Output is correct
5 Correct 9 ms 14428 KB Output is correct
6 Correct 8 ms 14428 KB Output is correct
7 Correct 7 ms 14428 KB Output is correct
8 Correct 9 ms 14428 KB Output is correct
9 Correct 7 ms 14428 KB Output is correct
10 Correct 7 ms 14428 KB Output is correct
11 Correct 9 ms 14612 KB Output is correct
12 Correct 7 ms 14428 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 591 ms 15820 KB Output is correct
2 Correct 515 ms 15568 KB Output is correct
3 Correct 528 ms 15664 KB Output is correct
4 Correct 537 ms 15820 KB Output is correct
5 Correct 373 ms 15548 KB Output is correct
6 Correct 404 ms 15436 KB Output is correct
7 Correct 408 ms 15568 KB Output is correct
8 Correct 366 ms 15200 KB Output is correct
9 Correct 365 ms 15316 KB Output is correct
10 Correct 370 ms 15456 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1056 ms 25456 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1035 ms 49192 KB Time limit exceeded
2 Halted 0 ms 0 KB -