Submission #80155

#	Time	Username	Problem	Language	Result	Execution time	Memory
80155		aminra	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	222 ms	41540 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)1e6 + 7;
const int infint = (int)1e9;
ll T, h[MAXN], pwr[MAXN], base = 37;
string s;
void hsh()
{
	h[0] = (s[0] - 'a' + 1);
	for (int i = 1; i < s.size(); i++)
		h[i] = (h[i - 1] * base % MOD + (s[i] - 'a' + 1)) % MOD;
}
ll get(int l, int r)
{
	if(l > r)
		return -1;
	ll ans = h[r];
	if(l)
		ans -= h[l - 1] * pwr[r - l + 1] % MOD, ans = (ans + MOD) % MOD;
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	pwr[0] = 1;
	for (int i = 1; i < MAXN; i++)
		pwr[i] = pwr[i - 1] * base % MOD;
	cin >> T;
	for (int i = 0; i < T; i++)
	{
		cin >> s;
		hsh();
		ll cur = 0, ans = 0, c = 1;
		for (int i = 0; i < s.size(); i++)
			if(i < s.size() - i - 1 && get(cur, i) == get(s.size() - i - 1, s.size() - cur - 1))
			{
				ans += 2, cur = i + 1;
				if(i == s.size() - i - 2)
					c = 0;
			}
		cout << ans + c << "\n";
	}
}

Compilation message (stderr)

palindromic.cpp: In function 'void hsh()':
palindromic.cpp:13:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < s.size(); i++)
                  ~~^~~~~~~~~~
palindromic.cpp: In function 'int main()':
palindromic.cpp:38:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < s.size(); i++)
                   ~~^~~~~~~~~~
palindromic.cpp:39:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(i < s.size() - i - 1 && get(cur, i) == get(s.size() - i - 1, s.size() - cur - 1))
       ~~^~~~~~~~~~~~~~~~~~
palindromic.cpp:42:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(i == s.size() - i - 2)
        ~~^~~~~~~~~~~~~~~~~~~

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