Submission #113894

#	Time	Username	Problem	Language	Result	Execution time	Memory
113894		Mahdi_Jfri	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	136 ms	20652 KiB

palindromic

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int maxn = 1e6 + 20;
const int mod = 1e9 + 7;
const int base = 6985;

int h[maxn] , pw[maxn];

inline int get(int l , int r)
{
	return (h[r] - (1LL * h[l] * pw[r - l] % mod) + mod) % mod;
}

int getAns(int l , int r)
{
	if(l >= r)
		return 0;
	
	for(int i = 1; i <= r - l; i++)
		if(get(l , l + i) == get(r - i , r))
			return 1 + (i != r - l) + getAns(l + i , r - i);
}

int solve()
{
	string s;
	cin >> s;

	int n = s.size();

	for(int i = 0; i < n; i++)
		h[i + 1] = (1LL * h[i] * base + s[i]) % mod;

	cout << getAns(0 , n) << endl;

	return 0;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	pw[0] = 1;
	for(int i = 1; i < maxn; i++)
		pw[i] = 1LL * pw[i - 1] * base % mod;

	int t;
	cin >> t;

	while(t--)
		solve();
}

Compilation message (stderr)

palindromic.cpp: In function 'int getAns(int, int)':
palindromic.cpp:25:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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