Submission #974518

#	Time	Username	Problem	Language	Result	Execution time	Memory
974518		kilkuwu	Palindromes (APIO14_palindrome)	C++17	100 / 100	562 ms	53904 KiB

palindrome

#include <bits/stdc++.h>

#define nl '\n'

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

namespace hash {
using u64 = uint64_t;
using u32 = uint32_t;
constexpr int kSeed = -1;  // change this to fixed seed for predictable base
constexpr u64 kAlpha = 1000000007;  // the value is from 0 -> kAlphabet - 1
constexpr u64 kMod = (1ULL << 61) - 1;
static_assert(kMod - kAlpha > 2);
// randomly getting an odd base from kAlpha + 1 -> kMod - 1
u64 get_random_base(u64 not_this = -1) {
  std::mt19937_64 h_rng(
      kSeed == -1
          ? std::chrono::high_resolution_clock::now().time_since_epoch().count()
          : kSeed);
  auto rd = std::uniform_int_distribution<u64>(kAlpha + 2, kMod - 1);
  u64 base = rd(h_rng);
  base -= base % 2 == 0;
  while (base == not_this) {
    base = rd(h_rng);
    base -= base % 2 == 0;
  }
  return base;
}
u64 mul(u64 a, u64 b) {
  u64 l1 = (u32)a, h1 = a >> 32, l2 = (u32)b, h2 = b >> 32;
  u64 l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2;
  u64 ret = (l & kMod) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
  ret = (ret & kMod) + (ret >> 61);
  ret = (ret & kMod) + (ret >> 61);
  return ret - 1;
}
u64 add(u64 a, u64 b) { return a += b, a -= (a >= kMod) * kMod; }
u64 sub(u64 a, u64 b) { return a + (a < b) * kMod - b; }
u64 p = get_random_base(), q = get_random_base(p);
std::vector<u64> pp(1, 1), qq(1, 1);
void ensure_pp_size(int size) {
  while ((int)pp.size() < size) pp.emplace_back(mul(pp.back(), p));
}
void ensure_qq_size(int size) {
  while ((int)qq.size() < size) qq.emplace_back(mul(qq.back(), q));
}
struct FwdHash {
  std::vector<u64> hf;
  FwdHash() = default;
  template <typename String>
  FwdHash(const String& s) : hf(s.size() + 1) {
    ensure_pp_size(s.size() + 1);
    for (int i = 0; i < (int)s.size(); i++) {
      hf[i + 1] = add(mul(hf[i], p), s[i] + 1);
    }
  }
  int size() const { return hf.size() - 1; }
  // NOTE: [l, r)
  u64 get_fwd(int l, int r) const { return sub(hf[r], mul(hf[l], pp[r - l])); }
  int operator[](int index) const { return get_fwd(index, index + 1) - 1; }
};
struct FBHash : FwdHash {
  std::vector<u64> hb;
  FBHash() = default;
  template <typename String>
  FBHash(const String& s) : FwdHash(s), hb(s.size() + 1) {
    for (int i = s.size() - 1; i >= 0; i--) {
      hb[i] = add(mul(hb[i + 1], p), s[i] + 1);
    }
  }
  // NOTE: [l, r)
  u64 get_bwd(int l, int r) const { return sub(hb[l], mul(hb[r], pp[r - l])); }
};
struct Hash2D {
  std::vector<std::vector<u64>> h;
  Hash2D() = default;
  template <typename String2D>
  Hash2D(const String2D& s)
      : h(s.size() + 1, std::vector<u64>(s[0].size() + 1)) {
    int n = s.size();
    int m = s[0].size();
    ensure_pp_size(n + 1);
    ensure_qq_size(m + 1);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        h[i + 1][j + 1] = add(mul(h[i + 1][j], q), s[i][j] + 1);
      }
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        h[i][j] = add(mul(h[i - 1][j], p), h[i][j]);
      }
    }
  }
  // NOTE: [x, u) * [y, v)
  u64 get(int x, int y, int u, int v) {
    auto res = sub(h[u][v], mul(h[x][v], pp[u - x]));
    res = sub(res, mul(h[u][y], qq[v - y]));
    return add(res, mul(mul(h[x][y], pp[u - x]), qq[v - y]));
  }
};
// NOTE: [l1, h1.size()) and [l2, h2.size())
int longest_common_prefix(const FwdHash& h1, const FwdHash& h2, int l1,
                          int l2) {
  int lb = 0, rb = std::min(h1.size() - l1, h2.size() - l2) + 1;
  while (lb < rb - 1) {
    int mb = (lb + rb) / 2;
    if (h1.get_fwd(l1, l1 + mb) == h2.get_fwd(l2, l2 + mb)) {
      lb = mb;
    } else {
      rb = mb;
    }
  }
  return lb;
}
// NOTE: [0, r1) and [0, r2)
int longest_common_suffix(const FwdHash& h1, const FwdHash& h2, int r1,
                          int r2) {
  int lb = 0, rb = std::min(r1, r2) + 1;
  while (lb < rb - 1) {
    int mb = (lb + rb) / 2;
    if (h1.get_fwd(r1 - mb, r1) == h2.get_fwd(r2 - mb, r2)) {
      lb = mb;
    } else {
      rb = mb;
    }
  }
  return lb;
}
// NOTE: [l1, r1) and [l2, r2)
bool is_smaller(const FwdHash& h1, const FwdHash& h2, int l1, int r1, int l2,
                int r2) {
  int lcp = longest_common_prefix(h1, h2, l1, l2);
  int len1 = r1 - l1;
  int len2 = r2 - l2;
  int min_len = std::min(len1, len2);
  return lcp >= min_len ? len1 < len2 : h1[l1 + lcp] < h2[l2 + lcp];
}
}  // namespace hash

using hash::FBHash;
using hash::FwdHash;
using hash::Hash2D;

namespace suffarr {
std::vector<int> sa_is(const std::vector<int>& s, int upper) {
  int n = int(s.size());
  if (n == 0) return {};
  if (n == 1) return {0};
  if (n == 2) {
    if (s[0] < s[1]) {
      return {0, 1};
    } else {
      return {1, 0};
    }
  }
  std::vector<int> sa(n);
  std::vector<bool> ls(n);
  for (int i = n - 2; i >= 0; i--)
    ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]);
  std::vector<int> sl(upper + 1), ss(upper + 1);
  for (int i = 0; i < n; i++) {
    if (!ls[i])
      ss[s[i]]++;
    else
      sl[s[i] + 1]++;
  }
  for (int i = 0; i <= upper; i++) {
    ss[i] += sl[i];
    if (i < upper) sl[i + 1] += ss[i];
  }
  auto induce = [&](const std::vector<int>& lms) {
    std::fill(sa.begin(), sa.end(), -1);
    std::vector<int> bb(upper + 1);
    std::copy(ss.begin(), ss.end(), bb.begin());
    for (auto d : lms) {
      if (d == n) continue;
      sa[bb[s[d]]++] = d;
    }
    std::copy(sl.begin(), sl.end(), bb.begin());
    sa[bb[s[n - 1]]++] = n - 1;
    for (int i = 0; i < n; i++) {
      int v = sa[i];
      if (v >= 1 && !ls[v - 1]) sa[bb[s[v - 1]]++] = v - 1;
    }
    std::copy(sl.begin(), sl.end(), bb.begin());
    for (int i = n - 1; i >= 0; i--) {
      int v = sa[i];
      if (v >= 1 && ls[v - 1]) sa[--bb[s[v - 1] + 1]] = v - 1;
    }
  };
  std::vector<int> lmp(n + 1, -1);
  int m = 0;
  for (int i = 1; i < n; i++) {
    if (!ls[i - 1] && ls[i]) lmp[i] = m++;
  }
  std::vector<int> lms;
  lms.reserve(m);
  for (int i = 1; i < n; i++) {
    if (!ls[i - 1] && ls[i]) lms.push_back(i);
  }
  induce(lms);
  if (!m) return sa;
  std::vector<int> sorted_lms;
  sorted_lms.reserve(m);
  for (int v : sa) {
    if (lmp[v] != -1) sorted_lms.push_back(v);
  }
  std::vector<int> rec_s(m);
  int rec_upper = 0;
  rec_s[lmp[sorted_lms[0]]] = 0;
  for (int i = 1; i < m; i++) {
    int l = sorted_lms[i - 1], r = sorted_lms[i];
    int end_l = (lmp[l] + 1 < m) ? lms[lmp[l] + 1] : n;
    int end_r = (lmp[r] + 1 < m) ? lms[lmp[r] + 1] : n;
    bool same = true;
    if (end_l - l != end_r - r) {
      same = false;
    } else {
      while (l < end_l) {
        if (s[l] != s[r]) break;
        l++;
        r++;
      }
      if (l == n || s[l] != s[r]) same = false;
    }
    if (!same) rec_upper++;
    rec_s[lmp[sorted_lms[i]]] = rec_upper;
  }
  auto rec_sa = sa_is(rec_s, rec_upper);
  for (int i = 0; i < m; i++) {
    sorted_lms[i] = lms[rec_sa[i]];
  }
  induce(sorted_lms);
  return sa;
}

std::vector<int> suffix_array(const std::vector<int>& s, int upper) {
  assert(0 <= upper);
  for (int d : s) assert(0 <= d && d <= upper);
  return suffarr::sa_is(s, upper);
}

template <class T>
std::vector<int> suffix_array(const std::vector<T>& s) {
  int n = int(s.size());
  std::vector<int> ord(n);
  iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), [&](int l, int r) { return s[l] < s[r]; });
  std::vector<int> s2(n);
  int now = 0;
  for (int i = 0; i < n; i++) {
    if (i && s[ord[i - 1]] != s[ord[i]]) now++;
    s2[ord[i]] = now;
  }
  return suffarr::sa_is(s2, now);
}

std::vector<int> suffix_array(const std::string& s) {
  int n = int(s.size());
  std::vector<int> s2(n);
  for (int i = 0; i < n; i++) s2[i] = s[i];
  return suffarr::sa_is(s2, 255);
}

template <class T>
std::vector<int> lcp_array(const std::vector<T>& s,
                           const std::vector<int>& sa) {
  int n = int(s.size());
  assert(n >= 1);
  std::vector<int> rnk(n);
  for (int i = 0; i < n; i++) rnk[sa[i]] = i;
  std::vector<int> lcp(n - 1);
  int h = 0;
  for (int i = 0; i < n; i++) {
    if (h > 0) h--;
    if (rnk[i] == 0) continue;
    int j = sa[rnk[i] - 1];
    for (; j + h < n && i + h < n; h++) {
      if (s[j + h] != s[i + h]) break;
    }
    lcp[rnk[i] - 1] = h;
  }
  return lcp;
}

std::vector<int> lcp_array(const std::string& s, const std::vector<int>& sa) {
  int n = int(s.size());
  std::vector<int> s2(n);
  for (int i = 0; i < n; i++) s2[i] = s[i];
  return lcp_array(s2, sa);
}
}  // namespace suffarr

using suffarr::lcp_array;
using suffarr::suffix_array;

template <typename T, typename F>
struct SparseTable {
  std::vector<std::vector<T>> t;

  SparseTable() {}
  SparseTable(const std::vector<T>& a) : t(std::__lg(a.size()) + 1) {
    t[0] = a;
    for (int k = 0; k + 1 < (int)t.size(); k++) {
      t[k + 1].resize(a.size() - (1 << (k + 1)) + 1);
      for (int i = 0; i < (int)t[k + 1].size(); i++)
        t[k + 1][i] = F()(t[k][i], t[k][i + (1 << k)]);
    }
  }

  // NOTE: [l, r)
  T query(int l, int r) {
    int k = std::__lg(r - l);
    return F()(t[k][l], t[k][r - (1 << k)]);
  }
};

template <typename T>
struct MinMerge {
  T operator()(const T& a, const T& b) { return std::min<T>(a, b); }
};

template <typename T>
using MinSparseTable = SparseTable<T, MinMerge<T>>;

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

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

  // we get all unique palindromes

  struct Palindrome {
    int m1, m2, len;
  };

  std::set<uint64_t> palin_hashes;
  std::vector<Palindrome> unique_palins;

  auto is_palindrome = [&](int l, int r) -> bool {
    return hasher.get_fwd(l, r) == hasher.get_bwd(l, r);
  };

  auto add_all = [&](int m1, int m2) {
    int lb = 0, rb = std::min(m1 + 1, n - m2) + 1;

    while (lb < rb - 1) {
      int mb = (lb + rb) / 2;
      if (is_palindrome(m1 - mb + 1, m2 + mb)) {
        lb = mb;
      } else {
        rb = mb;
      }
    }

    int len = lb;
    while (len > 0) {
      auto hsh = hasher.get_fwd(m1 - len + 1, m2 + len);
      auto it = palin_hashes.insert(hsh);
      if (it.second == false) break;
      unique_palins.push_back({m1, m2, len});
      len--;
    }
  };

  for (int i = 0; i < n; i++) {
    add_all(i, i);
    if (i + 1 < n) {
      add_all(i, i + 1);
    }
  }

  auto sa = suffix_array(s);
  auto lcp = lcp_array(s, sa);

  std::vector<int> pos(n);

  for (int i = 0; i < n; i++) {
    pos[sa[i]] = i;
  }

  MinSparseTable<int> tab(lcp);

  dbg(sa);
  dbg(lcp);

  /*
  2 bbbc
  1 bbc
  0 bc
    c
  */

  auto count_occurrence = [&](int l, int r) -> int {
    int len = r - l;

    l = pos[l];
    int upper = l;
    int lb = 0, rb = l - 1;

    while (lb <= rb) {
      int mb = (lb + rb) / 2;
      int val = tab.query(mb, l);
      if (val >= len) {
        upper = mb;
        rb = mb - 1;
      } else {
        lb = mb + 1;
      }
    }

    int lower = l;
    lb = l + 1, rb = n - 1;

    while (lb <= rb) {
      int mb = (lb + rb) / 2;
      int val = tab.query(l, mb);

      if (val >= len) {
        lower = mb;
        lb = mb + 1;
      } else {
        rb = mb - 1;
      }
    }

    dbg(lower, upper);
    return lower - upper + 1;
  };

  // b, b, b, c

  int64_t ans = -1;
  for (auto [m1, m2, len] : unique_palins) {
    int lb = m1 - len + 1, rb = m2 + len;
    len = rb - lb;
    dbg(lb, rb);
    ans = std::max(ans, (int64_t)len * count_occurrence(lb, rb));
  }

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

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