Submission #1261691

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261691		kaiboy	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	70 ms	11080 KiB

palindromic

#include <algorithm>
#include <iostream>
#include <cstring>

using namespace std;

const int N = 1000000;
const int M = N * 2 + 1;

char cc[N + 1], cc_[M];
int rr[M];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int t; cin >> t;
	while (t--) {
		cin >> cc;
		int n = strlen(cc), m = 0; cc_[m++] = ' ';
		for (int i = 0, j = n - 1; i < j; i++, j--) {
			cc_[m++] = cc[i];
			cc_[m++] = ' ';
			cc_[m++] = cc[j];
			cc_[m++] = ' ';
		}
		for (int o = 0, i = 0, j = 0; i < m; i++)
			if (o * 2 - i >= 0 && i + rr[o * 2 - i] < j)
				rr[i] = rr[o * 2 - i];
			else {
				j = max(j, (o = i) + 1);
				while (0 <= o * 2 - j && j < m && cc_[j] == cc_[o * 2 - j])
					j++;
				rr[i] = j - o;
			}
		int k = 0, i_ = 0;
		for (int i = 2; i <= n; i += 2)
			if (rr[i_ + i] > i - i_)
				k += 2, i_ = i;
		if (i_ < n)
			k++;
		cout << k << '\n';
	}
	return 0;
}

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