Submission #1247426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247426		MateiKing80	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	200 ms	26812 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll

const int N = 1e6 + 5;
const int mod = 1e9 + 9, baza = 53;
int ibaza;

int lgpow(int b, int e) {
	if (e == 0)
		return 1;
	int x = lgpow(b, e >> 1);
	x = x * x % mod;
	if (e & 1)
		return x * b % mod;
	return x;
}

int put[N], iput[N], hsh[N];

int hs(int l, int r) {
	return (hsh[r] - hsh[l - 1] + mod) * iput[l] % mod;
}

bool eq(int l1, int r1, int l2, int r2) {
	return hs(l1, r1) == hs(l2, r2);
}

void solve() {
	string s;
	cin >> s;
	int n = s.size();
	s = "#" + s;
	hsh[0] = 0;
	int pt = 1;
	for (int i = 1; i <= n; i ++) {
		pt = pt * baza % mod;
		hsh[i] = (hsh[i - 1] + pt * (s[i] - 'a' + 1) % mod) % mod;
	}
	int ans = 1, l = 1, r = 1;
	while (r <= n / 2) {
		if (eq(l, r, n - r + 1, n - l + 1)) {
			ans += 2;
			l = r + 1;
			r = r + 1;
			continue;
		} else {
			r ++;
		}
	}
	if (l == n / 2 + 1 && r == n / 2 + 1 && n % 2 == 0)
		ans --;
	cout << ans << '\n';
}

signed main() {
	put[0] = 1;
	iput[0] = 1;
	ibaza = lgpow(baza, mod - 2);
	for (int i = 1; i < N; i ++)
		put[i] = put[i - 1] * baza % mod;
	for (int i = 1; i < N; i ++)
		iput[i] = iput[i - 1] * ibaza % mod;
	int t;
	cin >> t;
	while (t --)
		solve();
}

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