제출 #23265

#제출 시각아이디문제언어결과실행 시간메모리
23265Nurlykhan회문 (APIO14_palindrome)C++14
47 / 100
1000 ms14892 KiB
#include <bits/stdc++.h> #define pii pair<int, int> #define f first #define s second #define pb push_back #define mp make_pair #define ll long long #define ld long double #define sz(v) int(v.size()) #define all(v) v.begin(), v.end() using namespace std; const int N = (int) 3e5 + 10; const int M = (int) 2e6 + 10; const ll LINF = (ll) 1e18; const int INF = (int) 1e9 + 7; const double EPS = (double) 1e-9; string st; ll ans; int h[N], h1[N]; int p[N]; inline int get_hash(const int &l, const int &r) { int ans = (h[r] - (l ? h[l - 1] : 0) + INF); if (ans >= INF) ans -= INF; ans = ans * 1ll * p[sz(st) - 1 - r] % INF; return ans; } inline int get_revhash(const int &l, const int &r) { int ans = (h1[l] - h1[r + 1] + INF); if (ans >= INF) ans -= INF; ans = ans * 1ll * p[l] % INF; return ans; } inline int first_diff(const pii &x, const pii &y) { int l = 0, r = min(x.s - x.f, y.s - y.f); int neq = -1; while (l <= r) { int m = (l + r) / 2; if (get_hash(x.f, x.f + m) == get_hash(y.f, y.f + m)) { l = m + 1; } else { neq = m; r = m - 1; } } return neq; } bool cmp(pii x, pii y) { int neq = first_diff(x, y); if (neq == -1) return x.s - x.f < y.s - y.f; return st[x.f + neq] < st[y.f + neq]; } vector<int> get_shit1(vector<int> v) { vector<int> st, ret(sz(v)); for (int i = 0; i < sz(v); i++) { while (!st.empty() && v[i] <= v[st.back()]) st.pop_back(); ret[i] = st.empty() ? 0 : st.back() + 1; st.pb(i); } return ret; } vector<int> get_shit2(vector<int> v) { vector<int> st, ret(sz(v)); for (int i = sz(v) - 1; i >= 0; i--) { while (!st.empty() && v[i] <= v[st.back()]) st.pop_back(); ret[i] = st.empty() ? sz(v) - 1 : st.back() - 1; st.pb(i); } return ret; } void solve_odd() { vector<pii> v; for (int i = 0; i < sz(st); i++) { int l = 0, r = sz(st); int j = 0; while (l <= r) { int m = (l + r) / 2; if (i - m >= 0 && i + m < sz(st) && get_hash(i, i + m) == get_revhash(i - m, i)) { l = m + 1; j = m; } else { r = m - 1; } } v.pb(mp(i, i + j)); } sort(all(v), cmp); //for (auto it : v) cout << it << endl; cout << "-----\n"; vector<int> lcp(sz(v) - 1); for (int i = 0; i + 1 < sz(v); i++) { lcp[i] = first_diff(v[i], v[i + 1]); if (lcp[i] == -1) lcp[i] = min(v[i].s - v[i].f, v[i + 1].s - v[i + 1].f) + 1; } for (int i = 0; i < sz(v); i++) { ans = max(ans, 2ll * (v[i].s - v[i].f + 1) - 1); } vector<int> tmp1 = get_shit1(lcp); vector<int> tmp2 = get_shit2(lcp); for (int i = 0; i < sz(lcp); i++) { int occurs = tmp2[i] - tmp1[i] + 2; ans = max(ans, occurs * 1ll * (lcp[i] * 2 - 1)); } } void solve_even() { vector<pii> v; for (int i = 0; i < sz(st); i++) { int l = 0, r = sz(st); int j = -1; while (l <= r) { int m = (l + r) / 2; if (i - 1 - m >= 0 && i + m < sz(st) && get_hash(i, i + m) == get_revhash(i - 1 - m, i - 1)) { l = m + 1; j = m; } else { r = m - 1; } } if (j != -1) v.pb(mp(i, i + j)); } if (v.empty()) return; sort(all(v), cmp); vector<int> lcp(sz(v) - 1); //for (auto it : v) cout << it << endl; cout << "-----\n"; for (int i = 0; i + 1 < sz(v); i++) { lcp[i] = first_diff(v[i], v[i + 1]); if (lcp[i] == -1) lcp[i] = min(v[i].s - v[i].f, v[i + 1].s - v[i + 1].f) + 1; } for (int i = 0; i < sz(v); i++) { ans = max(ans, 2ll * (v[i].s - v[i].f + 1)); } vector<int> tmp1 = get_shit1(lcp); vector<int> tmp2 = get_shit2(lcp); for (int i = 0; i < sz(lcp); i++) { int occurs = tmp2[i] - tmp1[i] + 2; ans = max(ans, occurs * 2ll * lcp[i]); } } int main() { #define fn "balls" #ifdef witch freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #else // freopen(fn".in", "r", stdin); // freopen(fn".out", "w", stdout); #endif cin >> st; p[0] = 1; for (int i = 1; i < sz(st); i++) { p[i] = p[i - 1] * 37LL % INF; } for (int i = 0; i < sz(st); i++) { if (i) { h[i] = h[i - 1]; } h[i] = (h[i] + (st[i] - 'a' + 1) * 1LL * p[i]) % INF; } for (int i = sz(st) - 1; i >= 0; i--) { h1[i] = (h1[i + 1] + (st[i] - 'a' + 1) * 1ll * p[sz(st) - 1 - i]) % INF; } solve_odd(); solve_even(); 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...