Submission #45434

#TimeUsernameProblemLanguageResultExecution timeMemory
45434sorry_BenqPalindromic Partitions (CEOI17_palindromic)C++17
0 / 100
10010 ms376 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 5, sigma = 26; int len[maxn], link[maxn], to[maxn][sigma]; int slink[maxn], diff[maxn], series_ans[maxn]; int sz, last, n; char s[maxn]; void init() { n = 0; s[n++] = -1; link[0] = 1; len[1] = -1; sz = 2; } int get_link(int v) { while(s[n - len[v] - 2] != s[n - 1]) v = link[v]; return v; } void add_letter(char c) { //cout << "ADD_LETTER " << n << endl; s[n++] = c -= 'a'; last = get_link(last); if(!to[last][c]) { len[sz] = len[last] + 2; link[sz] = to[get_link(link[last])][c]; diff[sz] = len[sz] - len[link[sz]]; if(diff[sz] == diff[link[sz]]) slink[sz] = slink[link[sz]]; else slink[sz] = link[sz]; to[last][c] = sz++; } last = to[last][c]; } int main() { ios::sync_with_stdio(0); cin.tie(0); int T; cin >> T; for (int testcase = 0; testcase < T; testcase++){ init(); string t; cin >> t; string s; for (int i = 0; i < t.size() / 2; i++){ s += t[i]; s += t[t.size() - i - 1]; } if (t.size() % 2 == 1){ s += t[t.size() / 2]; } int N = s.size(); int ans[N + 1]; memset(ans, 0, sizeof(ans)); ans[0] = 0; int res = 0; for(int i = 1; i <= N; i++) { add_letter(s[i - 1]); //cout << "FOR LOOP " << n << endl; for(int v = last; len[v] > 0; v = link[v]) if (len[v] % 2 == 0) ans[i] = max(ans[i], ans[i - len[v]] + 2); if (i != n){ res = max(res, ans[i] + 1); } else{ res = max(res, ans[i]); } } cout << res << endl; } return 0; }

Compilation message (stderr)

palindromic.cpp: In function 'void add_letter(char)':
palindromic.cpp:31:19: warning: array subscript has type 'char' [-Wchar-subscripts]
     if(!to[last][c])
                   ^
palindromic.cpp:34:46: warning: array subscript has type 'char' [-Wchar-subscripts]
         link[sz] = to[get_link(link[last])][c];
                                              ^
palindromic.cpp:40:19: warning: array subscript has type 'char' [-Wchar-subscripts]
         to[last][c] = sz++;
                   ^
palindromic.cpp:42:22: warning: array subscript has type 'char' [-Wchar-subscripts]
     last = to[last][c];
                      ^
palindromic.cpp: In function 'int main()':
palindromic.cpp:55:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < t.size() / 2; i++){
                   ~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...