Submission #44682

#TimeUsernameProblemLanguageResultExecution timeMemory
44682bogdan10bosPalindromic Partitions (CEOI17_palindromic)C++14
60 / 100
10066 ms18408 KiB
#include <bits/stdc++.h> using namespace std; //#define FILE_IO typedef pair<char, char> pcc; typedef long long LL; const int base = 31; int N; int dp[1000005]; char s[1000005]; LL pw[1000005], hsh[1000005]; vector<int> mp[35][35]; int get_hash(int st, int dr) { return hsh[dr] - hsh[st - 1] * pw[dr - st + 1]; } void solve_test() { scanf("%s", s + 1); N = strlen(s + 1); for(int i = 1; i <= N; i++) hsh[i] = (1LL * hsh[i - 1] * base) + s[i] - 'a' + 1; int ans = 1; for(int i = 0; i < 26; i++) for(int j = 0; j < 26; j++) mp[i][j].clear(); for(int st = 1, dr = N; st < dr; st++, dr--) { dp[st] = 0; for(auto pos: mp[s[dr] - 'a'][s[st] - 'a']) { int lgt = st - pos + 1; if(dp[pos - 1] > 0 && get_hash(pos, st) == get_hash(dr, dr + lgt - 1)) dp[st] = max(dp[st], dp[pos - 1] + 2); } if(get_hash(1, st) == get_hash(dr, N)) dp[st] = max(dp[st], 2); if(s[st] == s[dr] && dp[st - 1]) dp[st] = max(dp[st], dp[st - 1] + 2); ans = max(ans, dp[st] + (st + 1 < dr ? 1 : 0)); if(dp[st - 1] != 0) mp[s[st] - 'a'][ s[dr] - 'a'].push_back(st); } printf("%d\n", ans); } int main() { #ifdef FILE_IO freopen("1.in", "r", stdin); freopen("1.out", "w", stdout); #endif pw[0] = 1; int N = 1e6; for(int i = 1; i <= N; i++) pw[i] = 1LL * pw[i - 1] * base; int T; scanf("%d\n", &T); for(int t = 1; t <= T; t++) solve_test(); return 0; }

Compilation message (stderr)

palindromic.cpp: In function 'void solve_test()':
palindromic.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s + 1);
     ~~~~~^~~~~~~~~~~~~
palindromic.cpp: In function 'int main()':
palindromic.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d\n", &T);
     ~~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...