oj.uz

Submission #971467

# Submission time Handle Problem Language Result Execution time Memory
971467 2024-04-28T14:59:52 Z kilkuwu Palindromes (APIO14_palindrome) C++17
47 / 100
 1000 ms 40200 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23900 KB Output is correct
2 Correct 11 ms 23896 KB Output is correct
3 Correct 11 ms 23896 KB Output is correct
4 Correct 12 ms 23900 KB Output is correct
5 Correct 11 ms 23816 KB Output is correct
6 Correct 12 ms 23896 KB Output is correct
7 Correct 13 ms 23900 KB Output is correct
8 Correct 12 ms 23896 KB Output is correct
9 Correct 11 ms 23904 KB Output is correct
10 Correct 11 ms 23896 KB Output is correct
11 Correct 11 ms 23900 KB Output is correct
12 Correct 11 ms 23900 KB Output is correct
13 Correct 11 ms 23900 KB Output is correct
14 Correct 11 ms 23900 KB Output is correct
15 Correct 12 ms 23964 KB Output is correct
16 Correct 11 ms 23896 KB Output is correct
17 Correct 11 ms 23900 KB Output is correct
18 Correct 11 ms 23768 KB Output is correct
19 Correct 11 ms 24280 KB Output is correct
20 Correct 11 ms 24200 KB Output is correct
21 Correct 11 ms 24068 KB Output is correct
22 Correct 11 ms 24152 KB Output is correct
23 Correct 11 ms 24156 KB Output is correct
24 Correct 12 ms 24216 KB Output is correct
25 Correct 12 ms 24156 KB Output is correct
26 Correct 13 ms 24076 KB Output is correct
27 Correct 11 ms 24156 KB Output is correct
28 Correct 12 ms 24156 KB Output is correct
29 Correct 11 ms 24204 KB Output is correct
30 Correct 13 ms 23900 KB Output is correct
31 Correct 13 ms 23900 KB Output is correct
32 Correct 13 ms 24080 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 26400 KB Output is correct
2 Correct 18 ms 26456 KB Output is correct
3 Correct 21 ms 26460 KB Output is correct
4 Correct 18 ms 26204 KB Output is correct
5 Correct 21 ms 26460 KB Output is correct
6 Correct 22 ms 26340 KB Output is correct
7 Correct 17 ms 26460 KB Output is correct
8 Correct 19 ms 26456 KB Output is correct
9 Correct 17 ms 25948 KB Output is correct
10 Correct 15 ms 24216 KB Output is correct
11 Correct 18 ms 24156 KB Output is correct
12 Correct 18 ms 25988 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 674 ms 28348 KB Output is correct
2 Correct 584 ms 28412 KB Output is correct
3 Correct 861 ms 28316 KB Output is correct
4 Correct 760 ms 28368 KB Output is correct
5 Correct 486 ms 28220 KB Output is correct
6 Correct 487 ms 28496 KB Output is correct
7 Correct 515 ms 28332 KB Output is correct
8 Correct 475 ms 25268 KB Output is correct
9 Correct 466 ms 25432 KB Output is correct
10 Correct 506 ms 28376 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1061 ms 31396 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1059 ms 40200 KB Time limit exceeded
2 Halted 0 ms 0 KB -