oj.uz

Submission #882993

# Submission time Handle Problem Language Result Execution time Memory
882993 2023-12-04T11:19:12 Z nguyentunglam Palindromes (APIO14_palindrome) C++17
100 / 100
 542 ms 41904 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 : 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]);
      }

      for(int &j : add[i]) {
        j = root(j);
        cnt[j]++;
        ret = max(ret, 1LL * (i * 2 + k) * cnt[j]);
      } add[i].clear();
    }
    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(pos[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(pos[i]);
  }

  long long ans2 = calc(0);

  cout << max(ans1, ans2);
}

Compilation message

palindrome.cpp: In function 'int32_t main()':
palindrome.cpp:109:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |       int mid = l + r >> 1;
      |                 ~~^~~
palindrome.cpp:123:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  123 |       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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19124 KB Output is correct
2 Correct 4 ms 19056 KB Output is correct
3 Correct 4 ms 19032 KB Output is correct
4 Correct 3 ms 19036 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 19128 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 4 ms 19036 KB Output is correct
10 Correct 4 ms 19036 KB Output is correct
11 Correct 4 ms 19036 KB Output is correct
12 Correct 4 ms 19032 KB Output is correct
13 Correct 4 ms 19036 KB Output is correct
14 Correct 4 ms 19036 KB Output is correct
15 Correct 5 ms 19052 KB Output is correct
16 Correct 4 ms 19036 KB Output is correct
17 Correct 4 ms 19036 KB Output is correct
18 Correct 5 ms 19036 KB Output is correct
19 Correct 4 ms 19288 KB Output is correct
20 Correct 6 ms 19292 KB Output is correct
21 Correct 5 ms 19036 KB Output is correct
22 Correct 4 ms 19096 KB Output is correct
23 Correct 4 ms 19036 KB Output is correct
24 Correct 4 ms 19036 KB Output is correct
25 Correct 4 ms 19100 KB Output is correct
26 Correct 4 ms 19044 KB Output is correct
27 Correct 4 ms 19044 KB Output is correct
28 Correct 4 ms 19040 KB Output is correct
29 Correct 4 ms 19036 KB Output is correct
30 Correct 4 ms 19044 KB Output is correct
31 Correct 4 ms 19044 KB Output is correct
32 Correct 4 ms 19040 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19040 KB Output is correct
2 Correct 4 ms 19040 KB Output is correct
3 Correct 5 ms 19036 KB Output is correct
4 Correct 4 ms 19232 KB Output is correct
5 Correct 5 ms 19196 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 4 ms 19092 KB Output is correct
10 Correct 4 ms 19288 KB Output is correct
11 Correct 5 ms 19036 KB Output is correct
12 Correct 5 ms 19036 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19800 KB Output is correct
2 Correct 11 ms 19548 KB Output is correct
3 Correct 11 ms 19804 KB Output is correct
4 Correct 11 ms 19548 KB Output is correct
5 Correct 11 ms 19548 KB Output is correct
6 Correct 11 ms 19548 KB Output is correct
7 Correct 10 ms 19548 KB Output is correct
8 Correct 8 ms 19296 KB Output is correct
9 Correct 7 ms 19292 KB Output is correct
10 Correct 11 ms 19368 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 29008 KB Output is correct
2 Correct 110 ms 26972 KB Output is correct
3 Correct 108 ms 29008 KB Output is correct
4 Correct 96 ms 27232 KB Output is correct
5 Correct 119 ms 25852 KB Output is correct
6 Correct 114 ms 26080 KB Output is correct
7 Correct 98 ms 25948 KB Output is correct
8 Correct 49 ms 25540 KB Output is correct
9 Correct 101 ms 26060 KB Output is correct
10 Correct 115 ms 26068 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 41648 KB Output is correct
2 Correct 334 ms 32944 KB Output is correct
3 Correct 343 ms 41904 KB Output is correct
4 Correct 317 ms 34216 KB Output is correct
5 Correct 469 ms 33632 KB Output is correct
6 Correct 367 ms 32680 KB Output is correct
7 Correct 345 ms 32168 KB Output is correct
8 Correct 153 ms 31396 KB Output is correct
9 Correct 153 ms 31672 KB Output is correct
10 Correct 542 ms 33448 KB Output is correct
11 Correct 424 ms 39584 KB Output is correct
12 Correct 364 ms 31432 KB Output is correct