oj.uz

Submission #1015776

# Submission time Handle Problem Language Result Execution time Memory
1015776 2024-07-06T18:36:32 Z joelgun14 Palindromes (APIO14_palindrome) C++17
73 / 100
 1000 ms 113400 KB 
// header file
#include <bits/stdc++.h>
// pragma
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
// macros
#define endl "\n"
#define ll long long
#define mp make_pair
#define ins insert
#define lb lower_bound
#define pb push_back
#define ub upper_bound
#define lll __int128
#define fi first
#define se second
using namespace std;
typedef uint64_t H;
int mod = 1e9 + 9, mod2 = 1e9 + 7;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
static const H C = rng() % mod, C2 = rng() % mod2;
struct HashInterval {
  vector<H> ha, pw;
  HashInterval(string& str) : ha(str.size()+1), pw(ha) {
    pw[0] = 1;
    for(int i = 0; i < str.size(); ++i) {
      ha[i + 1] = (ha[i] * C + str[i]) % mod;
      pw[i + 1] = (pw[i] * C) % mod;
    }
  }
  H hashInterval(int a, int b) {
    if(a < 0 || a >= b || b >= ha.size())
      assert(false);
    return (ha[b] - ha[a] * pw[b - a]) % mod >= 0 ? (ha[b] - ha[a] * pw[b - a]) % mod : ((ha[b] - ha[a] * pw[b - a]) % mod) + mod;
  }
};
struct HashInterval2 {
  vector<H> ha, pw;
  HashInterval2(string& str) : ha(str.size()+1), pw(ha) {
    pw[0] = 1;
    for(int i = 0; i < str.size(); ++i) {
      ha[i + 1] = (ha[i] * C2 + str[i]) % mod2;
      pw[i + 1] = (pw[i] * C2) % mod2;
    }
  }
  H hashInterval(int a, int b) {
    if(a < 0 || a >= b || b >= ha.size())
      assert(false);
    return (ha[b] - ha[a] * pw[b - a]) % mod2 >= 0 ? (ha[b] - ha[a] * pw[b - a]) % mod2 : ((ha[b] - ha[a] * pw[b - a]) % mod2) + mod2;
  }
};
int main() {
  ios_base::sync_with_stdio(0); cin.tie(NULL);
  string s;
  cin >> s;
  string t = s;
  reverse(t.begin(), t.end());
  HashInterval norm(s), rev(t);
  HashInterval2 norm2(s), rev2(t);
  int n = s.size();
  set<pair<H, H>> even_hash, odd_hash;
  map<pair<H, H>, int> even_cnt, odd_cnt, even_sz, odd_sz;
  map<pair<H, H>, vector<pair<H, H>>> even_edges, odd_edges;
  for(int i = 0; i < n; ++i) {
    if(i + 1 < n && s[i] == s[i + 1]) {
      // even size
      int l = 1, r = n, ans = 1;
      while(l <= r) {
        int mid = (l + r) / 2;
        if(i + mid + 1 <= n && i - mid >= -1 && norm2.hashInterval(i + 1, i + mid + 1) == rev2.hashInterval(n - i - 1, n - i - 1 + mid) && norm.hashInterval(i + 1, i + mid + 1) == rev.hashInterval(n - i - 1, n - i - 1 + mid))
          l = mid + 1, ans = mid;
        else
          r = mid - 1;
      }
      pair<H, H> cur = mp(norm.hashInterval(i + 1, i + 1 + ans), norm2.hashInterval(i + 1, i + 1 + ans));
      ++even_cnt[cur];   
      even_sz[cur] = 2 * ans;
      even_hash.insert(cur);
      while(ans-- != 1 && !even_edges[cur].size())
        even_edges[cur].pb(mp(norm.hashInterval(i + 1, i + 1 + ans), norm2.hashInterval(i + 1, i + 1 + ans))), even_hash.insert(mp(norm.hashInterval(i + 1, i + 1 + ans), norm2.hashInterval(i + 1, i + 1 + ans))), cur = mp(norm.hashInterval(i + 1, i + 1 + ans), norm2.hashInterval(i + 1, i + 1 + ans)), even_sz[cur] = 2 * ans;
    }
    // odd size
    int l = 1, r = n, ans = 1;
    while(l <= r) {
      int mid = (l + r) / 2;
      if(i + mid <= n && i - mid >= -1 && norm2.hashInterval(i, i + mid) == rev2.hashInterval(n - i - 1, n - i - 1 + mid) && norm.hashInterval(i, i + mid) == rev.hashInterval(n - i - 1, n - i - 1 + mid))
        l = mid + 1, ans = mid;
      else
        r = mid - 1;
    }
    pair<H, H> cur = mp(norm.hashInterval(i, i + ans), norm2.hashInterval(i, i + ans));
    ++odd_cnt[cur];   
    odd_sz[cur] = 2 * ans - 1;
    // cout << "DEB " << i << " " << odd_sz[cur] << endl;
    odd_hash.insert(cur);
    while(ans-- != 1 && !odd_edges[cur].size())
      odd_edges[cur].pb(mp(norm.hashInterval(i, i + ans), norm2.hashInterval(i, i + ans))), odd_hash.insert(mp(norm.hashInterval(i, i + ans), norm2.hashInterval(i, i + ans))), cur = mp(norm.hashInterval(i, i + ans), norm2.hashInterval(i, i + ans)), odd_sz[cur] = 2 * ans - 1;
  }
  // process by largest size hash first
  vector<pair<int, pair<H, H>>> v;
  ll res = 0;
  for(auto x : odd_hash)
    v.pb(mp(odd_sz[x], x));
  sort(v.begin(), v.end());
  reverse(v.begin(), v.end());
  for(auto x : v) {
    // cout << x.fi << " " << odd_cnt[x.se] << endl;
    res = max(res, 1ll * x.fi * odd_cnt[x.se]);
    for(auto y : odd_edges[x.se]) {
      // cout << "FROM " << x.se << " TO " << y << endl;
      odd_cnt[y] += odd_cnt[x.se];
    }
  }
  v.clear();
  for(auto x : even_hash) 
    v.pb(mp(even_sz[x], x));
  sort(v.begin(), v.end());
  reverse(v.begin(), v.end());
  for(auto x : v) {
    res = max(res, 1ll * x.fi * even_cnt[x.se]);
    for(auto y : even_edges[x.se]) {
      even_cnt[y] += even_cnt[x.se];
    }
  }
  cout << res << endl;
  return 0;
}

Compilation message

palindrome.cpp: In constructor 'HashInterval::HashInterval(std::string&)':
palindrome.cpp:26:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i = 0; i < str.size(); ++i) {
      |                    ~~^~~~~~~~~~~~
palindrome.cpp: In member function 'H HashInterval::hashInterval(int, int)':
palindrome.cpp:32:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long unsigned int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     if(a < 0 || a >= b || b >= ha.size())
      |                           ~~^~~~~~~~~~~~
palindrome.cpp: In constructor 'HashInterval2::HashInterval2(std::string&)':
palindrome.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i = 0; i < str.size(); ++i) {
      |                    ~~^~~~~~~~~~~~
palindrome.cpp: In member function 'H HashInterval2::hashInterval(int, int)':
palindrome.cpp:47:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long unsigned int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     if(a < 0 || a >= b || b >= ha.size())
      |                           ~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 604 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4436 KB Output is correct
2 Correct 22 ms 4384 KB Output is correct
3 Correct 26 ms 4184 KB Output is correct
4 Correct 23 ms 4168 KB Output is correct
5 Correct 16 ms 4180 KB Output is correct
6 Correct 17 ms 4308 KB Output is correct
7 Correct 22 ms 4380 KB Output is correct
8 Correct 2 ms 1116 KB Output is correct
9 Correct 3 ms 1116 KB Output is correct
10 Correct 11 ms 3104 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 39732 KB Output is correct
2 Correct 344 ms 39624 KB Output is correct
3 Correct 341 ms 38096 KB Output is correct
4 Correct 400 ms 38348 KB Output is correct
5 Correct 288 ms 38852 KB Output is correct
6 Correct 190 ms 30400 KB Output is correct
7 Correct 270 ms 33372 KB Output is correct
8 Correct 26 ms 7260 KB Output is correct
9 Correct 77 ms 14348 KB Output is correct
10 Correct 232 ms 34076 KB Output is correct

Subtask #5
0 / 27.0

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