Submission #45428

#	Time	Username	Problem	Language	Result	Execution time	Memory
45428		sorry_Benq	Palindromic Partitions (CEOI17_palindromic)	C++17	0 / 100	10067 ms	376 KiB

palindromic

#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 3e5 + 1, 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()
{
    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)
{
    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]);
			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:29:19: warning: array subscript has type 'char' [-Wchar-subscripts]
     if(!to[last][c])
                   ^
palindromic.cpp:32:46: warning: array subscript has type 'char' [-Wchar-subscripts]
         link[sz] = to[get_link(link[last])][c];
                                              ^
palindromic.cpp:38:19: warning: array subscript has type 'char' [-Wchar-subscripts]
         to[last][c] = sz++;
                   ^
palindromic.cpp:40:22: warning: array subscript has type 'char' [-Wchar-subscripts]
     last = to[last][c];
                      ^
palindromic.cpp: In function 'int main()':
palindromic.cpp:53:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < t.size() / 2; i++){
                   ~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 20
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40