Submission #230645

#	Time	Username	Problem	Language	Result	Execution time	Memory
230645		islingr	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	109 ms	22160 KiB

palindromic

#include <iostream>
using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define trav(x, v) for (auto &x : v)

#define sz(x) int((x).size())

using ll = long long;
constexpr ll p = 5, M = 1e9 + 7, N = 1 << 20;

string s; int n;
ll pp[N], pref[N];

void init() {
	rep(i, 0, n) pref[i + 1] = (pref[i] + pp[i] * (s[i] - 'a' + 1)) % M;
}

ll hsh(int l, int r) { // [l, r]
	int ret = pref[r + 1] - pref[l];
	ret = ret * pp[n - l] % M;
	if (ret < 0) ret += M;
	return ret;
}

int solve() {
	cin >> s; n = sz(s);
	init();
	int cnt = 0;
	int x = 0, y = n - 1;
	while (x <= y) {
		// cerr << x << ' ' << y << '\n';
		int l = x, r = y;
		bool found = false;
		while (l < r) {
			if (hsh(x, l) == hsh(r, y)) {
				cnt += 2;
				found = true;
				break;
			}
			++l, --r;
		}
		if (!found) {
			++cnt;
			break;
		}
		x = l + 1;
		y = r - 1;
	}
	return cnt;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	pp[0] = 1;
	rep(i, 1, N) pp[i] = p * pp[i - 1] % M;

	int t; cin >> t;
	while (t--) cout << solve() << '\n';
}

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