Submission #829109

#TimeUsernameProblemLanguageResultExecution timeMemory
829109NhanBeooPalindromes (APIO14_palindrome)C++17
23 / 100
1079 ms7924 KiB
// Judges with GCC >= 12 only needs Ofast // #pragma GCC optimize("Ofast") #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize") // MLE optimization // #pragma GCC optimize("conserve-stack") // Old judges // #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2") // New judges. Test with assert(__builtin_cpu_supports("avx2")); // #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native") // Atcoder // #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma") #include <bits/stdc++.h> using namespace std; #define int ll #define MAX LLONG_MAX #define st first #define nd second #define endl '\n' #define SZ(x) ((int)x.size()) #define ALL(x) x.begin(), x.end() typedef long long ll; typedef pair< int, int > ii; typedef pair< int, ii > iii; typedef vector< int > vi; typedef vector< ii > vii; typedef vector< iii > viii; typedef vector< vi > vvi; typedef vector< vii > vvii; typedef vector< viii > vviii; const int N = 3e5 + 5; int n; int base = 311; int mod = 1000000007; string s, t; int hashS[N], hashT[N], power[N]; unordered_map<int, int> m; int ans = 0; int palind(int l, int r){ // int ans; // for(int k=0; k<3; k++){ int tmp1 = (hashS[r] - hashS[l-1] * power[r-l+1] + mod * mod) % mod; int tmp2 = (hashT[n-l+1] - hashT[n-r] * power[r-l+1] + mod * mod) % mod; if(tmp1 != tmp2) return -1; // if(k == 2) ans = tmp1; // } return tmp1; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> s; t = s; reverse(ALL(t)); n = SZ(s); s = ' ' + s; t = ' ' + t; // for(int i=0; i<3; i++){ power[0] = 1; for(int j=1; j<=n; j++) power[j] = (power[j-1] * base) % mod; hashS[0] = s[0]; for(int j=1; j<=n; j++) hashS[j] = (hashS[j-1] * base + s[j]) % mod; hashT[0] = t[0]; for(int j=1; j<=n; j++) hashT[j] = (hashT[j-1] * base + t[j]) % mod; // } for(int len=1; len<=n; len++){ for(int i=1; i+len-1<=n; i++){ int hashed = palind(i, i+len-1); if(hashed != -1) m[hashed]++; } for(auto tmp: m){ int cnt = tmp.nd; ans = max(ans, len * cnt); } m.clear(); } cout << ans; }
#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...