Submission #1026972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026972		mnbvcxz123	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	147 ms	12136 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll P = 69421;
const ll M = 1e9 + 9;

int main() {
	int tc;
	cin >> tc;
	while (tc--) {
		string s;
		cin >> s;

		int n = s.length();
		int ans = 0;
		int found = 0;  // -1 if no further strings can be found on both side
		int start = 0;  // index we start searching from

		while (found != -1) {
			ll hash_left = 0, hash_right = 0;
			found = -1;
			for (ll l = start, pw = 1; l < n / 2; l++, pw = (pw * P % M)) {
				hash_left = (hash_left * P + s[l]) % M;
				hash_right = (hash_right + pw * s[n - 1 - l]) % M;
				if (hash_left == hash_right) {
					found = l;
					break;
				}
			}

			if (found != -1) {
				start = found + 1;
				ans += 2;
			}
		}

		if (start * 2 == n) {
			cout << ans << endl;
		} else {
			cout << ans + 1 << endl;
		}
	}
}

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