제출 #299284

#제출 시각아이디문제언어결과실행 시간메모리
299284AaronNaidu회문 (APIO14_palindrome)C++14
8 / 100
1035 ms2204 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll mod1 = 1000000009; string s; ll n; ll prefSums[20000], sufSums[20000]; ll pows[20000]; unordered_map<ll, ll> m; ll divide1(ll num, ll den) { while (num < 0) { num += mod1; } while (den < 0) { den += mod1; } ll inv = 1; ll exp = den; exp %= mod1; for (int i = 0; i < 32; i++) { if ((mod1-2) & (1<<i)) { inv *= exp; inv %= mod1; } exp *= exp; exp %= mod1; } ll ans = num * inv; ans %= mod1; return ans; } int main() { cin >> s; ll thisPow = 1; n = s.length(); for (int i = 0; i < n; i++) { pows[i]= thisPow; thisPow *= 11; thisPow %= mod1; } prefSums[0] = s[0] - 'a' + 1; for (int i = 1; i < n; i++) { prefSums[i] = prefSums[i-1] + (s[i] - 'a' + 1) * pows[i]; prefSums[i] %= mod1; } sufSums[n-1] = s[n-1] - 'a' + 1; for (int i = n-2; i >= 0; i--) { sufSums[i] = sufSums[i+1] + (s[i] - 'a' + 1) * pows[n-1-i]; sufSums[i] %= mod1; } ll totMax = 0; for (int j = 0; j < n-1; j++) { if (prefSums[j] == divide1(sufSums[0]-sufSums[j+1], pows[n-1-j])) { ll curr = 0; auto z = m.find(prefSums[j]); if (z != m.end()) { curr =z->second; m.erase(z); } curr += j+1; totMax = max(totMax, curr); m.insert({prefSums[j], curr}); } } if (prefSums[n-1] == sufSums[0]) { ll curr = 0; auto z = m.find(prefSums[n-1]); if (z != m.end()) { curr =z->second; m.erase(z); } curr += n; totMax = max(totMax, curr); m.insert({prefSums[n-1], curr}); } for (int i = 1; i < n; i++) { for (int j = i; j < n-1; j++) { if (divide1(prefSums[j]-prefSums[i-1], pows[i]) == divide1(sufSums[i]-sufSums[j+1], pows[n-1-j])) { ll curr = 0; auto z = m.find(divide1(prefSums[j]-prefSums[i-1], pows[i])); if (z != m.end()) { curr = z->second; m.erase(z); } curr += j-i+1; totMax = max(totMax, curr); m.insert({divide1(prefSums[j]-prefSums[i-1], pows[i]), curr}); } } if (divide1(prefSums[n-1]-prefSums[i-1], pows[i]) == sufSums[i]) { ll curr = 0; auto z = m.find(sufSums[i]); if (z != m.end()) { curr = z->second; m.erase(z); } curr += n-i; totMax = max(totMax, curr); m.insert({sufSums[i], curr}); } } cout << totMax << "\n"; }
#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...