Submission #299095

#TimeUsernameProblemLanguageResultExecution timeMemory
299095AaronNaiduPalindromes (APIO14_palindrome)C++14
0 / 100
1091 ms2588 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll mod1 = 1000000007; ll mod2 = 1000000009; string s; ll n; ll prefSums[20000], sufSums[20000]; ll pows[20000]; unordered_map<ll, ll> m; 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; } /*for (int j = 0; j < n; j++) { cout << prefSums[j] << " "; //cout << prefSums[j] << " " << sufSums[j] << "\n"; } cout << "\n"; for (int i = 1; i < n; i++) { for (int j = i; j < n; j++) { cout << (prefSums[j] - prefSums[i-1]) / pows[i] << " "; } cout << "\n"; } cout << "\n"; for (int i = 0; i < n; i++) { for (int j = i; j < n-1; j++) { cout << (sufSums[i] - sufSums[j+1]) / pows[n-1-j] << " "; } cout << sufSums[i]; cout << "\n"; }*/ ll totMax = 0; for (int j = 0; j < n-1; j++) { if (prefSums[j] == (sufSums[0]-sufSums[j+1])/pows[n-1-j]) { ll curr = 0; if (m.find(prefSums[j]) != m.end()) { curr = m.find(prefSums[j])->second; m.erase(prefSums[j]); } curr += j+1; totMax = max(totMax, curr); m.insert({prefSums[j], curr}); } } if (prefSums[n-1] == sufSums[0]) { ll curr = 0; if (m.find(prefSums[n-1]) != m.end()) { curr = m.find(prefSums[n-1])->second; m.erase(prefSums[n-1]); } 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 ((prefSums[j]-prefSums[i-1])/pows[i] == (sufSums[i]-sufSums[j+1])/pows[n-1-j]) { ll curr = 0; if (m.find((prefSums[j]-prefSums[i-1])/pows[i]) != m.end()) { curr = m.find((prefSums[j]-prefSums[i-1])/pows[i])->second; m.erase((prefSums[j]-prefSums[i-1])/pows[i]); } curr += j-i+1; totMax = max(totMax, curr); m.insert({(prefSums[j]-prefSums[i-1])/pows[i], curr}); } } if ((prefSums[n-1]-prefSums[i-1])/pows[i] == sufSums[i]) { ll curr = 0; if (m.find(sufSums[i]) != m.end()) { curr = m.find(sufSums[i])->second; m.erase(sufSums[i]); } 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...