Submission #1186021

#TimeUsernameProblemLanguageResultExecution timeMemory
1186021thieunguyenhuyPalindromes (APIO14_palindrome)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h> using namespace std; #define POPCOUNT(n) (__builtin_popcountll((n))) #define CLZ(n) (__builtin_clzll((n))) #define CTZ(n) (__builtin_ctzll((n))) #define LOG(n) (63 - __builtin_clzll((n))) #define BIT(n, i) (((n) >> (i)) & 1ll) #define MASK(i) (1ll << (i)) #define FLIP(n, i) ((n) ^ (1ll << (i))) #define ON(n, i) ((n) | MASK(i)) #define OFF(n, i) ((n) & ~MASK(i)) #define Int __int128 #define fi first #define se second #define hash pvhdeptrai typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<int, int> pii; typedef pair<long long, long long> pll; typedef pair<long long, int> pli; typedef pair<int, long long> pil; typedef vector<pair<int, int>> vii; typedef vector<pair<long long, long long>> vll; typedef vector<pair<long long, int>> vli; typedef vector<pair<int, long long>> vil; template <class T1, class T2> bool maximize(T1 &x, T2 y) { if (x < y) { x = y; return true; } return false; } template <class T1, class T2> bool minimize(T1 &x, T2 y) { if (x > y) { x = y; return true; } return false; } template <class T> void remove_duplicate(vector<T> &ve) { sort (ve.begin(), ve.end()); ve.resize(unique(ve.begin(), ve.end()) - ve.begin()); } mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); template <class T1, class T2> T1 random(T1 l, T2 r) { return uniform_int_distribution<T1>(l, r)(rng); } template <class T> T random(T r) { return rng() % r; } const int N = 6e5 + 5, LG = 20; const int MOD = 1e9 + 9; const int inf = 1e9; const long long INF = 1e18; const int base = 311; string s; int le[N], ri[N], pw[N]; int hash[N], rev_hash[N]; int rmq[N][LG]; struct SuffixArray { vector<int> sa, lcp, rank, w; vii pa; string str; int n; SuffixArray(string _s = "") { str = _s, n = str.size(); sa.assign(n, 0), lcp.assign(n, 0), rank.assign(n, 0), w.assign(n, 0); pa.assign(n, make_pair(0, 0)); get_sa(), get_lcp(); } void get_sa() { for (int i = 0; i < n; ++i) { sa[i] = i; pa[i] = make_pair(int(str[i]), 0); } auto cmp = [&](int x, int y) { return pa[x] < pa[y]; }; sort (sa.begin(), sa.end(), cmp); for (int len = 1; len <= n; len <<= 1) { int cnt = 0; for (int i = 0; i < n; ++i) { if (i > 0 && pa[sa[i - 1]] == pa[sa[i]]) w[sa[i]] = w[sa[i - 1]]; else w[sa[i]] = ++cnt; } if (cnt == n) break; for (int i = 0; i < n; ++i) { pa[i] = make_pair(w[i], (i + len < n ? w[i + len] : 0)); } sort (sa.begin(), sa.end(), cmp); } } void get_lcp() { for (int i = 0; i < n; ++i) rank[sa[i]] = i; for (int i = 0, k = 0; i < n; lcp[rank[i++]] = k) { if (rank[i] > 0) { int j = sa[rank[i] - 1]; if (k > 0) --k; while (str[i + k] == str[j + k]) ++k; } else k = 0; } } }; int getHash(int l, int r) { return (0ll + hash[r] - 1ll * hash[l - 1] * pw[r - l + 1] + 1ll * MOD * MOD) % MOD; } int get_revHash(int l, int r) { return (0ll + rev_hash[l] - 1ll * rev_hash[r + 1] * pw[r - l + 1] + 1ll * MOD * MOD) % MOD; } bool isPalin(int l, int r) { return getHash(l, r) == get_revHash(l, r); } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> s; string t(1, '#'); for (int i = 0; i < s.size(); ++i) { t += s[i]; t += '#'; } // cerr << "t = " << t << '\n'; int n = t.size(); SuffixArray T(t); for (int i = 0; i < n; ++i) rmq[i][0] = T.lcp[i]; for (int i = 1; i < LG; ++i) for (int j = 0; j + MASK(i) - 1 < n; ++j) { rmq[j][i] = min(rmq[j][i - 1], rmq[j + MASK(i - 1)][i - 1]); } auto get_lcp = [&](int l, int r) { ++l; int g = LOG(r - l + 1); return min(rmq[l][g], rmq[r - MASK(g) + 1][g]); }; pw[0] = 1; for (int i = 1; i <= n; ++i) pw[i] = 1ll * pw[i - 1] * base % MOD; hash[0] = t[0]; for (int i = 1; i < n; ++i) hash[i] = (1ll * hash[i - 1] * base + t[i]) % MOD; for (int i = n - 1; i >= 0; --i) rev_hash[i] = (1ll * rev_hash[i + 1] * base + t[i]) % MOD; ll ans = 0; for (int i = 0; i < n; ++i) { for (int len = max(0, T.lcp[T.rank[i]]); ; ++len) { if (i - len < 0 || i + len >= n) break; if (!isPalin(i - len, i + len)) break; int real_len = 2 * len + 1; if (t[i] == '#') { int x = (len / 2); real_len -= 2 * x + 1; } else { int x = (len + 1) / 2; real_len -= 2 * x; } int p = T.rank[i - len]; int low = 0, high = p - 1, L = p, R = p; while (low <= high) { int mid = (low + high) >> 1; if (get_lcp(mid, p) >= 2 * len + 1) high = (L = mid) - 1; else low = mid + 1; } low = p + 1, high = n - 1; while (low <= high) { int mid = (low + high) >> 1; if (get_lcp(p, mid) >= 2 * len + 1) low = (R = mid) + 1; else high = mid - 1; } maximize(ans, 1ll * real_len * (R - L + 1)); } } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...