Submission #1015761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015761		joelgun14	Palindromes (APIO14_palindrome)	C++17	0 / 100	1064 ms	91264 KiB

palindrome

// 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 ull;
int mod = 1e9 + 9;
struct H {
  ull x; H(ull x = 0) : x(x) {}
  H operator+ (H o) { return (x + o.x + (x + o.x < x)) % mod; }
  H operator- (H o) { return (*this + ~o.x); }
  H operator* (H o) { auto m = (x * o.x) % mod; return H(m); }
  ull get() const { return (x + !~x) % mod; }
  bool operator== (H o) const { return get() == o.get(); }
  bool operator< (H o) const {return get() < o.get(); }
};
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
static const H C = rng() % mod;
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];
      pw[i + 1] = pw[i] * C;
    }
  }
  H hashInterval(int a, int b) {
    if(a < 0 || a >= b || b >= ha.size())
      return -1;
    return ha[b] - ha[a] * pw[b - a];
  }
};
vector<H> getHashes(string &str, int length) {
  if(str.size() < length)
    return {};
    H h = 0, pw = 1;
    for(int i = 0; i < length; ++i) {
      h = h * C + str[i], pw = pw * C;
    }
    vector<H> ret = {h};
    for(int i = length; i < str.size(); ++i)
      ret.pb(h = h * C + str[i] - pw * str[i - length]);
    return ret;
}
H hashString(string& s) {H h{}; for(char c : s) h = h * C + c; return h;}
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);
  int n = s.size();
  set<H> even_hash, odd_hash;
  map<H, int> even_cnt, odd_cnt, even_sz, odd_sz;
  map<H, vector<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 && 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;
      }
      H cur = norm.hashInterval(i + 1, i + 1 + ans);
      ++even_cnt[cur];   
      even_sz[cur] = 2 * ans;
      //cout << "DEB " << cur.x << " " << odd_sz[cur] << endl;
      even_hash.insert(cur);
      while(ans-- != 1 && !even_hash.count(norm.hashInterval(i + 1, i + 1 + ans)))
        even_edges[cur].pb(norm.hashInterval(i + 1, i + 1 + ans)), even_hash.insert(norm.hashInterval(i + 1, i + 1 + ans)), cur = norm.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 && norm.hashInterval(i, i + mid) == rev.hashInterval(n - i - 1, n - i - 1 + mid))
        l = mid + 1, ans = mid;
      else
        r = mid - 1;
    }
    H cur = norm.hashInterval(i, i + ans);
    ++odd_cnt[cur];   
    odd_sz[cur] = 2 * ans - 1;
    //cout << "DEB " << cur.x << " " << odd_sz[cur] << endl;
    odd_hash.insert(cur);
    while(ans-- != 1 && !odd_hash.count(norm.hashInterval(i, i + ans)))
      odd_edges[cur].pb(norm.hashInterval(i, i + ans)), odd_hash.insert(norm.hashInterval(i, i + ans)), cur = norm.hashInterval(i, i + ans), odd_sz[cur] = 2 * ans - 1;
  }
  // process by largest size hash first
  vector<pair<int, 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]) {
      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 (stderr)

palindrome.cpp: In constructor 'HashInterval::HashInterval(std::string&)':
palindrome.cpp:35:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i = 0; i < str.size(); ++i) {
      |                    ~~^~~~~~~~~~~~
palindrome.cpp: In member function 'H HashInterval::hashInterval(int, int)':
palindrome.cpp:41:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<H>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     if(a < 0 || a >= b || b >= ha.size())
      |                           ~~^~~~~~~~~~~~
palindrome.cpp: In function 'std::vector<H> getHashes(std::string&, int)':
palindrome.cpp:47:17: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |   if(str.size() < length)
      |      ~~~~~~~~~~~^~~~~~~~
palindrome.cpp:47:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   47 |   if(str.size() < length)
      |   ^~
palindrome.cpp:49:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   49 |     H h = 0, pw = 1;
      |     ^
palindrome.cpp:54:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i = length; i < str.size(); ++i)
      |                         ~~^~~~~~~~~~~~

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