Submission #309490

#	Time	Username	Problem	Language	Result	Execution time	Memory
309490		Kenzo_1114	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	569 ms	27112 KiB

palindromic

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000010;
const long long int MOD = 1e9 + 19;

int t;
long long int p[MAXN], sp[MAXN];
string s;	

void init()
{	
	p[0] = 1;
	for(int i = 1; i < MAXN; i++)
		p[i] = (p[i - 1] * 23) % MOD;
}

long long int H(int i, int j)
{
	long long int h = sp[j];
	if(i)	h = (h - sp[i - 1] + MOD) * p[i];
	return h % MOD;
}

void solve()
{
	cin >> s;

	int sz = (int) s.size();
	for(int i = 0; i < sz; i++)
	{	
		sp[i] = (p[sz - i - 1] * (s[i] - 'a')) % MOD;
		if(i)	sp[i] = (sp[i - 1] + sp[i]) % MOD;
	}

	int l = 0, r = sz - 1, ans = 0;
	while(l <= r)
	{
		if(l == r)	ans--;

		if(s[l] == s[r])	l++, r--;
		else
			for(int k = 1; l + k < sz; k++)
				if(H(l, l + k) == H(r - k, r))
				{	
					l += k + 1, r -= k + 1; 
					if(r < l - 1)	ans--;
					break;	
				}

		ans += 2;
	}

	printf("%d\n", ans);
}

int main ()
{
	init();

	scanf("%d", &t);
	while(t--)	solve();	
}

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |  scanf("%d", &t);
      |  ~~~~~^~~~~~~~~~

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