Submission #235836

#TimeUsernameProblemLanguageResultExecution timeMemory
235836balbitPalindromes (APIO14_palindrome)C++14
23 / 100
1100 ms8192 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int, int> #define f first #define s second #define REP(i,n) for (int i = 0; i<n; ++i) #ifdef BALBIT #define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__) template<typename T> void _do(T && x){cerr<<x<<endl;} template<typename T, typename ...S> void _do(T && x, S&&...y){cerr<<x<<", "; _do(y...);} #define IOS() #else #define IOS() ios::sync_with_stdio(0), cin.tie(0) #define endl '\n' #define bug(...) #endif // BALBIT #define SZ(x) (int)(x.size()) #define ALL(x) (x).begin(), (x).end() #define pb push_back const int B = 37; const ll mod = 1e9+87; const int maxn = 3e5; ll hv[maxn]; ll pB[maxn], ipB[maxn]; ll inv(ll b) { if (b == 1)return 1; return inv(mod%b) * (mod-mod/b) % mod; } signed main(){ IOS(); map<ll, ll> mp; string s;cin>>s; int n = SZ(s); pB[0] = ipB[0] = 1; for (int i = 1; i<=n; ++i) { pB[i] = pB[i-1] * B % mod; ipB[i] = inv(pB[i]); } bug(pB[2] * ipB[2] % mod); for (int i = 0; i<n; ++i) { hv[i+1] = hv[i] + pB[i] * (s[i] - 'a'+1); hv[i+1] %= mod; } for (int i = 0; i<n; ++i) { for (int j = 0; i-j>=0 && i+j < n && s[i-j] == s[i+j]; ++j) { mp[ (hv[i+j+1] - hv[i-j] + mod) % mod * ipB[i-j] % mod] += (j*2+1); } for (int j = 0; i-j>=0 && i+j+1 < n && s[i-j] == s[i+j+1]; ++j) { mp[ (hv[i+j+1+1] - hv[i-j] + mod) % mod * ipB[i-j] % mod] += (j*2+2); bug(j*2+2, (hv[i+j+1+1] - hv[i-j] + mod) % mod * ipB[i-j] % mod); } } ll re = 0; for (auto x : mp) { re = max(re, x.s); } cout<<re<<endl; }
#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...