Submission #971467

#	Time	Username	Problem	Language	Result	Execution time	Memory
971467		kilkuwu	Palindromes (APIO14_palindrome)	C++17	47 / 100	1061 ms	40200 KiB

palindrome

#include <bits/stdc++.h>

#define nl '\n'

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

template <int md, int base = 133>
struct Hash {
  std::vector<int> hsh, ppw;

  Hash(const std::string& s, int P = base) : hsh(s.size() + 1, 0), ppw(s.size() + 1, 1) {
    for (int i = 0; i < (int) s.size(); i++) {
      hsh[i + 1] = ((int64_t) hsh[i] * P + s[i]) % md;
      ppw[i + 1] = ((int64_t) ppw[i] * P) % md;
    }
  }

  int get(int l, int r) {
    int res = ((int64_t) hsh[r] - (int64_t) hsh[l] * ppw[r - l]) % md;
    return res + (res < 0) * md;
  }
};

const int md1 = 1000003, md2 = 1000033;
using H1 = Hash<1000003>;
using H2 = Hash<1000033, 311>;

std::vector<int> values[md1];
int cnt[md2];

const int mxN = 3e5 + 1;

std::pair<int, int> hv[mxN];
bool palin[mxN];

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  std::string s;
  std::cin >> s;
  int n = s.size();

  H1 h1(s);
  H2 h2(s);

  auto t = s;
  std::reverse(t.begin(), t.end());
  H1 h1r(t);
  H2 h2r(t);

  auto get = [&](int l, int r) -> std::pair<int, int> {
    return {h1.get(l, r), h2.get(l, r)};
  };

  auto get_r = [&](int l, int r) -> std::pair<int, int> {
    l = n - l;
    r = n - r;
    std::swap(l, r);
    return {h1r.get(l, r), h2r.get(l, r)};
  };

  int64_t ans = 0;

  for (int len = 1; len <= n; len++) {
    for (int j = 0; j + len - 1 < n; j++) {
      hv[j] = get(j, j + len);
      palin[j] = hv[j] == get_r(j, j + len);
      if (palin[j]) {
        values[hv[j].first].push_back(hv[j].second);
      }
    }

    for (int i = 0; i + len - 1 < n; i++) {
      if (!palin[i]) continue;
      palin[i] = 0;

      for (int v : values[hv[i].first]) {
        cnt[v]++; 
        ans = std::max(ans, (int64_t) cnt[v] * len);
      }

      for (int v : values[hv[i].first]) {
        cnt[v]--;
      }

      values[hv[i].first].clear();
      values[hv[i].first].shrink_to_fit();
    }
  }

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

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