Submission #1223023

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223023		radodododo	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	338 ms	26672 KiB

palindromic

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

long long mod = 1488148811;
long long p = 2585241;

vector<long long> h;
vector<long long> step;

long long hesh(long long l, long long r) {
	return ((h[r + 1] - (h[l] * step[r - l + 1]) % mod) % mod + mod) % mod;
}

int main() {
	long long t;
	cin >> t;
	step.resize(1000001);
	step[0] = 1;
	for (long long i = 1; i < 1000001; i++) {
		step[i] = (step[i - 1] * p) % mod;
	}
	for (long long gh = 0; gh < t; gh++) {
		long long n;
		string s;
		cin >> s;
		n = s.size();
		if (n == 1) {
			cout << 1 << '\n';
			continue;
		}
		h.assign(n + 1, 0);
		for (long long i = 0; i < n; i++) {
			h[i + 1] = ((h[i] * p) % mod + s[i]) % mod;
		}
		long long ans = 0;
		long long l1 = 0, r1 = 0, l2 = n - 1, r2 = n - 1;
		while (true) {
			if (hesh(l1, r1) == hesh(l2, r2)) {
				ans += 2;
				l1 = r1 + 1;
				r1++;
				r2 = l2 - 1;
				l2--;
			}
			else {
				r1++;
				l2--;
			}
			if ((l1 <= l2 && l2 <= r1) || (l1 <= r2 && r2 <= r1)) {
				ans++;
				break;
			}
			if (l1 > r2) {
				break;
			}
		}
		cout << ans << '\n';
	}
}

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