Submission #1261062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261062		kaiboy	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	3262 ms	29008 KiB

palindromic

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

using namespace std;

const int   N = 1000000;
const int  N_ = 1 << 20;
const int INF = 0x3f3f3f3f;

char cc[N + 1];
int sa[N], aa0[N], aa1[N], tt[N], kk[N + 2], st[N_ << 1], n_;

void compress(int n) {
	for (int a = 0, h = 0; h < n; h++)
		aa0[sa[h]] = h + 1 == n || aa0[sa[h]] < aa0[sa[h + 1]] || aa1[sa[h]] < aa1[sa[h + 1]] ? a++ : a;
}

void extend(int n, int m) {
	for (int i = 0; i < n; i++)
		aa1[i] = i + m < n ? aa0[i + m] : -1;
}

void sort(int *ii, int *jj, int *aa, int n) {
	for (int a = 0; a < n + 2; a++)
		kk[a] = 0;
	for (int i = 0; i < n; i++)
		kk[aa[i] + 2]++;
	for (int a = 1; a < n + 2; a++)
		kk[a] += kk[a - 1];
	for (int h = 0; h < n; h++)
		jj[kk[aa[ii[h]] + 1]++] = ii[h];
}

int query(int l, int r) {
	int x = INF;
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if (l & 1)
			x = min(x, st[l++]);
		if (!(r & 1))
			x = min(x, st[r--]);
	}
	return x;
}

int lcp(int i, int j) {
	int a = aa0[i], b = aa0[j];
	if (a > b)
		swap(a, b);
	return query(a, b - 1);
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int t; cin >> t;
	while (t--) {
		cin >> cc;
		int n = strlen(cc);
		for (int a = 0; a < n; a++)
			sa[a] = a;
		sort(sa, sa + n, [] (int i, int j) { return cc[i] < cc[j]; });
		for (int i = 0; i < n; i++)
			aa0[i] = cc[i], aa1[i] = 0;
		compress(n);
		for (int m = 1; m < n; m <<= 1) {
			extend(n, m);
			sort(sa, tt, aa1, n);
			sort(tt, sa, aa0, n);
			compress(n);
		}
		n_ = 1;
		while (n_ < n - 1)
			n_ <<= 1;
		for (int l = 0, i = 0; i < n; i++, l = max(l - 1, 0)) {
			int a = aa0[i];
			if (a + 1 < n) {
				for (int j = sa[a + 1]; i + l < n && cc[i + l] == cc[j + l]; l++)
					;
				st[a + n_] = l;
			}
		}
		for (int i = n_ - 1; i; i--) {
			int l = i << 1, r = l ^ 1;
			st[i] = min(st[l], st[r]);
		}
		int k = 0;
		for (int i = 0, j; i < n / 2; i = j, k += 2) {
			for (j = i + 1; j <= n / 2 && lcp(i, n - j) < j - i; j++)
				;
			if (j > n / 2) {
				k++;
				break;
			}
		}
		if (n % 2 && k % 2 == 0)
			k++;
		cout << k << '\n';
	}
	return 0;
}

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