Submission #982643

#TimeUsernameProblemLanguageResultExecution timeMemory
982643vjudge1Palindromic Partitions (CEOI17_palindromic)C++17
60 / 100
10033 ms53468 KiB
#include <bits/stdc++.h> #define pii pair<int,int> #define int long long #define ff first #define ss second using namespace std; const int mod = 1e9 + 7; const int p1 = 97; const int p2 = 107; const int binv = 268041239; const int binv2 = 224299067; const int maxn = 1e6; vector<int> pows(maxn+7,1); vector<int> invs(maxn+7,1); vector<int> pows2(maxn+7,1); vector<int> invs2(maxn+7,1); void init() { for (int i = 1; i < maxn; i++) pows[i] = pows[i-1]*p1%mod; for (int i = 1; i < maxn; i++) invs[i] = invs[i-1]*binv%mod; for (int i = 1; i < maxn; i++) pows2[i] = pows2[i-1]*p2%mod; for (int i = 1; i < maxn; i++) invs2[i] = invs2[i-1]*binv2%mod; } void solve() { string s; cin >> s; int n = s.length(); vector<int> dp(n/2+2,0); int back = n-1; vector<int> hash(n); hash[0] = s[0]*pows[0]%mod; for (int i = 1; i < n; i++) { hash[i] = hash[i-1] + (s[i]*pows[i]%mod); hash[i] %= mod; } vector<int> hash2(n); hash2[0] = s[0]*pows2[0]%mod; for (int i = 1; i < n; i++) { hash2[i] = hash2[i-1] + (s[i]*pows2[i]%mod); hash2[i] %= mod; } auto mile = [&](int i,int j) { pii base = {hash[j],hash2[j]}; if (i > 0) { base.ff-=hash[i-1]-2*mod; base.ss-=hash2[i-1]-2*mod; base.ff%=mod; base.ss%=mod; base.ff*=invs[i]; base.ss*=invs2[i]; base.ff%=mod; base.ss%=mod; } return ((pii)base); }; for (int i = 0; i < n/2+1; i++) { if (i >= back) break; for(int j = 0; j <= i; j++) { //cout << s.substr(j,i-j+1) << ' ' << s.substr(back,i-j+1) << " i: " << i << " j: " << j << '\n'; pii alpha = mile(j,i); pii sigma = mile(back,back+(i-j)); if (alpha == sigma) { if (j==0) dp[i] = max(dp[i],2ll); else if (dp[j-1] > 0) dp[i] = max(dp[i],dp[j-1]+2); } } back--; } int ans = 1; if (n%2) { for (int i = 0; i < n/2+1; i++) { ans = max(ans,dp[i]+1); } } else { for (int i = 0; i < n/2-1; i++) { ans = max(ans,dp[i]+1); } ans = max(ans,dp[n/2-1]); } cout << ans << '\n'; } signed main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; init(); while(t--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...