oj.uz

Submission #882990

# Submission time Handle Problem Language Result Execution time Memory
882990 2023-12-04T11:10:06 Z nguyentunglam Palindromes (APIO14_palindrome) C++17
0 / 100
 361 ms 41648 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 4 ms 18876 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 4 ms 19060 KB Output is correct
5 Correct 4 ms 19036 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 5 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 3 ms 19124 KB Output is correct
10 Incorrect 3 ms 19036 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Incorrect 5 ms 19036 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19804 KB Output is correct
2 Incorrect 12 ms 19568 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 28932 KB Output is correct
2 Incorrect 98 ms 26960 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 41648 KB Output is correct
2 Incorrect 326 ms 32944 KB Output isn't correct
3 Halted 0 ms 0 KB -