제출 #42259

#제출 시각아이디문제언어결과실행 시간메모리
42259fest회문 (APIO14_palindrome)C++14
0 / 100
530 ms50512 KiB
// fest #include <bits/stdc++.h> #define pb push_back #define F first #define S second #define y1 dasdasfasfas #define x1 wqdadfasfasfas #define All(c) c.begin(), c.end() #define SZ(A) (int((A).size())) #define umap unordered_map #define FILENAME "" #define __ fflush(stdout) typedef long long ll; typedef long double ld; using namespace std; void FREOPEN() { #ifdef COMP freopen(".in", "r", stdin); freopen("2.out", "w", stdout); #endif } inline double Time() {return (clock() * 1.0) / CLOCKS_PER_SEC; } const int N = 300500, M = 21, inf = 1e9 * 2, MOD = (int)1e9 + 7; char CH[N]; const ll INF = 1e18; const int dx[] = {1, -1, 0, 0, -1, 1, -1, 1}; const int dy[] = {0, 0, 1, -1, -1, 1, 1, -1}; int n; int pos[N], suff[N], c[M][N], new_suff[N], lcp[N], ans[N], dp[N], rev[N]; vector<int> go[N]; int range(int x) { while (x >= n) x -= n; while (x < 0) x += n; return x; } int main() { FREOPEN(); scanf("%s", CH); string s = CH; s += '#'; n = SZ(s); for (int i = 0; i < n; i++) { c[0][i] = (int)(s[i] - '#'); pos[c[0][i] + 1]++; } for (int i = 0; i < N - 1; i++) pos[i + 1] += pos[i]; for (int i = 0; i < n; i++) { suff[pos[c[0][i]]++] = i; } for (int len = 0; (1 << len) <= n; len++) { memset(pos, 0, sizeof(pos)); for (int i = 0; i < n; i++) { int f = range(suff[i] - (1 << len)); pos[c[len][f] + 1]++; } for (int i = 0; i < N - 1; i++) pos[i + 1] += pos[i]; for (int i = 0; i < n; i++) { int f = range(suff[i] - (1 << len)); new_suff[pos[c[len][f]]++] = f; } memcpy(suff, new_suff, sizeof(new_suff)); c[len + 1][suff[0]] = 0; int C = 0; for (int i = 1; i < n; i++) { int ff = range(suff[i - 1] + (1 << len)), ss = range(suff[i] + (1 << len)); if (c[len][suff[i - 1]] < c[len][suff[i]] || c[len][ff] < c[len][ss]) C++; c[len + 1][suff[i]] = C; } } for (int i = 1; i < n - 1; i++) { int p1 = suff[i], p2 = suff[i + 1]; for (int j = M - 1; j >= 0; j--) { if (max(p1, p2) + (1 << j) >= n) continue; if (c[j][p1] == c[j][p2]) { lcp[i] += (1 << j); p1 += (1 << j); p2 += (1 << j); } } } vector<pair<int, int> > st; for (int i = 1; i < n - 1; i++) { while (!st.empty() && st.back().F >= lcp[i]) st.pop_back(); if (!st.empty()) ans[suff[i]] -= st.back().S; st.pb({lcp[i], i}); } st.clear(); for (int i = n - 2; i >= 1; i--) { while (!st.empty() && st.back().F >= lcp[i]) st.pop_back(); if (!st.empty()) ans[suff[i]] += st.back().S - 1; else ans[suff[i]] += n - 2; st.pb({lcp[i], i}); } for (int i = 1; i < n; i++) rev[suff[i]] = i; ll out = 0; for (int i = 0, l = 0, r = 0; i < n - 1; i++) { dp[i] = 1; if (i <= r) dp[i] = min(dp[l + (r - i)], r - i + 1); while (i - dp[i] >= 0 && i + dp[i] < n - 1 && s[i - dp[i]] == s[i + dp[i]]) dp[i]++; if (i + dp[i] - 1 > r) l = i - dp[i] + 1, r = i + dp[i] - 1; out = max(out, dp[i] * 2ll - 1); } vector<int> st2; for (int l = 0; l < n - 1; l++) { int r = (l + l + lcp[rev[l]] - 1) / 2; while (!st2.empty() && st2.back() - dp[st2.back()] + 1 >= l - dp[l] + 1) st2.pop_back(); st2.pb(l); go[r].pb(l); while (!go[l].empty()) { int now = go[l].back(); go[l].pop_back(); int lef = 0; int rig = SZ(st2) - 1; int pos = -1; while (lef <= rig) { int mid = (lef + rig) / 2; if (st2[mid] - dp[st2[mid]] + 1 <= now) pos = st2[mid], lef = mid + 1; else rig = mid - 1; } if (pos >= now) out = max(out, ((pos - now) * 2 + 1) * 1ll * (ans[now] + 1)); } } st2.clear(); memset(dp, 0, sizeof(dp)); for (int i = 1, l = 0, r = 0; i < n - 1; i++) { if (s[i] != s[i - 1]) continue; dp[i] = 1; if (i <= r) dp[i] = min(dp[l + (r - i + 1)], r - i + 1); while (i - dp[i] - 1 >= 0 && i + dp[i] < n - 1 && s[i - dp[i] - 1] == s[i + dp[i]]) dp[i]++; if (i + dp[i] - 1 > r) l = i - dp[i], r = i + dp[i] - 1; out = max(out, dp[i] * 2ll); } for (int l = 1; l < n - 1; l++) { int r = (l + l + lcp[rev[l]]) / 2; while (!st2.empty() && st2.back() - dp[st2.back()] >= l - dp[l]) st2.pop_back(); st2.pb(l); go[r].pb(l); while (!go[l].empty()) { int now = go[l].back(); go[l].pop_back(); int lef = 0; int rig = SZ(st2) - 1; int pos = -1; while (lef <= rig) { int mid = (lef + rig) / 2; if (st2[mid] - dp[st2[mid]] <= now) pos = st2[mid], lef = mid + 1; else rig = mid - 1; } if (pos - 1 >= now) out = max(out, ((pos - now) * 2) * 1ll * (ans[now] + 1)); } } cout << out; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

palindrome.cpp: In function 'int main()':
palindrome.cpp:53:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", CH);
                 ^
#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...