| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 716685 | thiago_bastos | 회문 (APIO14_palindrome) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("tune=native")
#include "bits/stdc++.h"
using namespace std;
#define INF 1000000000
#define INFLL 1000000000000000000ll
#define EPS 1e-9
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define fi first
#define sc second
using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using ii = pair<int, int>;
using i128 = __int128;
struct Hash {
static const i64 P;
static i64 B;
vector<i64> pw, h;
i64 mul(i64 a, i64 b) {
i128 c = (i128)a * b;
c = (c & P) + (c >> 61);
if(c >= P) c -= P;
return c;
}
i64 sum(i64 a, i64 b) {
a += b;
if(a >= P) a -= P;
return a;
}
Hash(string& s) {
int n = s.size();
pw.resize(n + 1);
h.resize(n + 1);
pw[0] = 1;
h[0] = 0;
for(int i = 1; i <= n; ++i) {
pw[i] = mul(pw[i - 1], B);
h[i] = sum(h[i - 1], mul(pw[i], s[i - 1]));
}
}
i64 operator()(int l, int r) {
int n = pw.size();
return mul(pw[n-l-1], sum(h[r+1], P - h[l]));
}
};
mt19937 rng((int) chrono::steady_clock::now().time_since_epoch().count());
i64 uniform(i64 l, i64 r) {
uniform_int_distribution<i64> uid(l, r);
return uid(rng);
}
const i64 Hash :: P = (1ll << 61) - 1;
i64 Hash :: B = uniform(256, (1ll << 61) - 2);
i64 f(string& s) {
string t(rall(s));
Hash hs(s), ht(t);
using T = pair<int, i64>;
map<T, int, greater<T>> mp;
map<i64, ii> interval;
int n = s.size();
for(int i = 0; i < n; ++i) {
ii st[] = {{i, i}, {i, i + 1}};
for(auto [l, r] : st) {
if(s[l] != s[r]) continue;
int lo = 0, hi = min(l, n - r - 1) + 1;
while(lo < hi) {
int m = (lo + hi) / 2;
i64 h1 = hs(l - m, l);
i64 h2 = ht(n - r - m - 1, n - r - 1);
if(h1 != h2) hi = m;
else lo = m + 1;
}
--hi;
i64 h = hs(l - hi, r + hi);
interval[h] = {l - hi, r + hi};
++mp[{2 * hi + r - l + 1, h}];
}
}
i64 ans = 0;
while(!mp.empty()) {
auto [len, h] = mp.begin()->fi;
int frq = mp.begin()->sc;
ans = max(ans, (i64)len * frq);
mp.erase(mp.begin());
if(len <= 2) continue;
auto [l, r] = interval[h];
i64 nh = hs(l + 1, r - 1);
mp[{len - 2, nh}] += frq;
interval[nh] = {l + 1, r - 1};
}
return ans;
}
void solve() {
string s;
cin >> s;
cout << f(s) << '\n';
}
int main() {
ios_base :: sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin >> t;
while(t--) solve();
return 0;
}