Submission #882990

#	Time	Username	Problem	Language	Result	Execution time	Memory
882990		nguyentunglam	Palindromes (APIO14_palindrome)	C++17	0 / 100	361 ms	41648 KiB

palindrome

#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;

const int N = 3e5 + 10;

const long long base = 31, mod = 1e9 + 7;

long long f[N], g[N], p[N];

int pos[N], sa[N], tmp[N], lab[N], cnt[N], gap, n;

vector<int> event[N], add[N];

string s;

int get (int l, int r) {
  return (f[r] - f[l - 1] * p[r - l + 1] + mod * mod) % mod;
}

int _get(int l, int r) {
  return (g[l] - g[r + 1] * p[r - l + 1] + mod * mod) % mod;
}

bool cmp (int x, int y) {
  if (pos[x] != pos[y]) return pos[x] < pos[y];
  x += gap; y += gap;
  return x <= n && y <= n ? pos[x] < pos[y] : x > y;
}

int root(int v) {
  return lab[v] < 0 ? v : lab[v] = root(lab[v]);
}

int32_t main() {
  #define task ""

  cin.tie(0) -> sync_with_stdio(0);

  if (fopen("task.inp", "r")) {
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
  }

  if (fopen(task".inp", "r")) {
    freopen (task".inp", "r", stdin);
    freopen (task".out", "w", stdout);
  }

  cin >> s; s = " " + s;

  n = s.size() - 1;

  p[0] = 1;
  for(int i = 1; i <= n; i++) {
    p[i] = p[i - 1] * base % mod;
    f[i] = (f[i - 1] * base + s[i] - 'a' + 1) % mod;
  }

  for(int i = n; i >= 1; i--) {
    g[i] = (g[i + 1] * base + s[i] - 'a' + 1) % mod;
  }

  for(int i = 1; i <= n; i++) {
    pos[i] = s[i] - 'a' + 1;
    sa[i] = i;
  }

  for(gap = 1;; gap *= 2) {
    sort(sa + 1, sa + n + 1, cmp);
    for(int i = 1; i <= n; i++) tmp[i] = tmp[i - 1] + cmp(sa[i - 1], sa[i]);
    for(int i = 1; i <= n; i++) pos[sa[i]] = tmp[i];
    if (tmp[n] == n) break;
  }

  for(int i = 1, k = 0; i <= n; i++) if (pos[i] < n) {
    int j = sa[pos[i] + 1];
    while (s[i + k] == s[j + k]) k++;
    event[k].push_back(pos[i]);
    if (k) k--;
  }

  auto calc = [&] (int k) {
    long long ret = 0;
    for(int i = 1; i <= n; i++) lab[i] = -1, cnt[i] = 0;
    for(int i = n; i >= 1; i--) {
      for(int &j : add[i]) {
        j = root(j);
        cnt[j]++;
        ret = max(ret, 1LL * (i * 2 + k) * cnt[j]);
      } add[i].clear();
      for(int &j : event[i]) {
        int x = root(j), y = root(j + 1);
        if (lab[x] > lab[y]) swap(x, y);
        lab[x] += lab[y];
        lab[y] = x;
        cnt[x] += cnt[y];
        ret = max(ret, 1LL * (i * 2 + k) * cnt[x]);
      }
    }
    return ret;
  };

  for(int i = 1; i <= n; i++) {
    int l = 1, r = min(i, n - i + 1), last = 0;
    while (l <= r) {
      int mid = l + r >> 1;
      if (get(i - mid + 1, i) == _get(i, i + mid - 1)) {
        last = mid;
        l = mid + 1;
      } else r = mid - 1;
    }
    if (last) add[last].push_back(i);
  }

  long long ans1 = calc(-1);

  for(int i = 1; i <= n; i++) {
    int l = 1, r = min(i - 1, n - i + 1), last = 0;
    while (l <= r) {
      int mid = l + r >> 1;
      if (get(i - mid, i - 1) == _get(i, i + mid - 1)) {
        last = mid;
        l = mid + 1;
      } else r = mid - 1;
    }
    if (last) add[last].push_back(i);
  }

  long long ans2 = calc(0);

  cout << max(ans1, ans2);
}

Compilation message (stderr)

palindrome.cpp: In function 'int32_t main()':
palindrome.cpp:108:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |       int mid = l + r >> 1;
      |                 ~~^~~
palindrome.cpp:122:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  122 |       int mid = l + r >> 1;
      |                 ~~^~~
palindrome.cpp:42:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     freopen("task.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
palindrome.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     freopen("task.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
palindrome.cpp:47:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     freopen (task".inp", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
palindrome.cpp:48:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     freopen (task".out", "w", stdout);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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