제출 #42053

#제출 시각아이디문제언어결과실행 시간메모리
42053fest회문 (APIO14_palindrome)C++14
0 / 100
1067 ms1444 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 = 10500, M = 2, 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}; const int P[] = {2019, 2017}; const int mod[] = {(int)1e9 + 3, (int)1e9 + 9}; map<pair<int, int>, int> cnt; int h[M][N], pr[M][N], odd[N], even[N], nex_odd[N], nex_even[N]; int n; pair<int, int> get(int l, int r) { int f = ((h[0][r] - h[0][l - 1] + mod[0]) * 1ll * pr[0][n - l]) % mod[0]; int s = ((h[1][r] - h[1][l - 1] + mod[1]) * 1ll * pr[1][n - l]) % mod[1]; return {f, s}; } int main() { FREOPEN(); scanf("%s", CH); string s = CH; n = SZ(s); for (int j = 0; j < M; j++) { pr[j][0] = 1; for (int i = 1; i <= n; i++) pr[j][i] = (pr[j][i - 1] * 1ll * P[j]) % mod[j]; for (int i = 1; i <= n; i++) h[j][i] = (h[j][i - 1] + (s[i - 1] * 1ll * pr[j][i])) % mod[j]; } int ro = 0, re = 0; ll ans = 0; odd[ro++] = 1; cnt[get(1, 1)]++; for (int i = 2; i <= n; i++) { int nro = 0, nre = 0; for (int j = 0; j < ro; j++) { int p = odd[j]; if (p - (i - p) < 1) continue; if (s[p - (i - p) - 1] != s[i - 1]) continue; nex_odd[nro++] = p; cnt[get(p - (i - p), i)]++; ans = max(ans, cnt[get(p - (i - p), i)] * 1ll * ((i - p) * 2 + 1)); } for (int j = 0; j < re; j++) { int p = even[j]; if (p - (i - p + 1) < 1) continue; if (s[p - (i - p + 1) - 1] != s[i - 1]) continue; nex_even[nre++] = p; cnt[get(p - (i - p + 1), i)]++; ans = max(ans, cnt[get(p - (i - p + 1), i)] * 1ll * (i - p + 1) * 2ll); } nex_odd[nro++] = i; if (s[i - 1] == s[i - 2]) { nex_even[nre++] = i; cnt[get(i - 1, i)]++; ans = max(ans, cnt[get(i - 1, i)] * 2ll); } swap(nex_odd, odd); swap(nro, ro); swap(nex_even, even); swap(nre, re); } cout << ans; return 0; }

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

palindrome.cpp: In function 'int main()':
palindrome.cpp:55: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...