Submission #1163911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163911		canhnam357	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	528 ms	50340 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define int long long
#define MASK(i) (1LL << (i))
void ckmax(int& f, int s)
{
	f = (f > s ? f : s);
}
void ckmin(int& f, int s)
{
	f = (f < s ? f : s);
}
const int mod1 = 1035972859;
const int mod2 = 1704760909;
const int mod3 = 2137321811;
const int mod4 = 2002577573;
const int mod5 = 2143922441;
const int base = 256;
struct hashing
{
	int mod;
	vector<int> h, p, inv;
	hashing() {}
	hashing(int mod, string s)
	{
		int n = s.length();
		this->mod = mod;
		h.resize(n);
		p.resize(n);
		inv.resize(n);
		h[0] = s[0];
		p[0] = 1;
		for (int i = 1; i < n; i++)
		{
			p[i] = (p[i - 1] * base) % mod;
			h[i] = (h[i - 1] + s[i] * p[i]) % mod;
		}
		inv[n - 1] = power(p[n - 1], mod - 2);
		for (int i = n - 2; i >= 0; i--) inv[i] = (inv[i + 1] * base) % mod;
	}
	int power(int a, int b)
	{
		int ans = 1;
		while (b)
		{
			if (b & 1) ans = (ans * a) % mod;
			(a *= a) %= mod;
			b >>= 1;
		}
		return ans;
	}
	int get(int l, int r)
	{
		if (l > r) return 0;
		return l ? ((h[r] - h[l - 1] + mod) * inv[l]) % mod : h[r];
	}
	bool same(int l1, int r1, int l2, int r2)
	{
		return get(l1, r1) == get(l2, r2);
	}
};
void solve()
{
	string s;
	cin >> s;
	hashing h1(mod1, s), h2(mod2, s);
	int l = 0, r = s.size() - 1;
	int ans = 0;
	while (l <= r)
	{
		if (l == r)
		{
			ans++;
			break;
		}
		int has = 0;
		for (int i = l; r - (i - l) > i; i++)
		{
			if (h1.same(l, i, r - (i - l), r) && h1.same(l, i, r - (i - l), r)) 
			{
				r -= i - l + 1;
				l = i + 1;
				ans += 2;
				has = 1;
				break;
			}
		}
		if (!has)
		{
			ans++;
			break;
		}
	}
	cout << ans << '\n';
}
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while (t--) solve();
	return 0;
}

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