Submission #365047

#	Time	Username	Problem	Language	Result	Execution time	Memory
365047		saleh	Palindromes (APIO14_palindrome)	C++17	0 / 100	1087 ms	15092 KiB

palindrome

#include <bits/stdc++.h>

#define int long long
#define ft first
#define sd second

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 300 * 1000 + 1 + 23, D = 1000 * 1000 * 1000 + 123, B = 29;















string s;
int n, chi, o[MAXN], val[MAXN], tmp[MAXN], h[MAXN], tav[MAXN], tool[MAXN], ans;

int get(int l, int r) {
	return (h[r] - h[l] * tav[r - l] % D) % D;
}
bool cl(pii x, pii y) {
	int l = 0, r = min(x.sd - x.ft, y.sd - y.ft) + 1;
	while (r - l > 1) {
		int mid = ((r + l) >> 1);
		if (get(x.ft, x.ft + mid) == get(y.ft, y.ft + mid)) l = mid;
		else r = mid;
	}
	if (l == min(x.sd - x.ft, y.sd - y.ft)) return (x.sd - x.ft) < (y.sd - y.ft);
	return s[x.ft + r] < s[y.ft + r];
}
bool clp(pii x, pii y) {
	int l = 0, r = min(x.sd - x.ft, y.sd - y.ft) + 1;
	while (r - l > 1) {
		int mid = ((r + l) >> 1);
		if (get(x.ft, x.ft + mid) == get(y.ft, y.ft + mid)) l = mid;
		else r = mid;
	}
	if (l == y.sd - y.ft) return true;
	return false;
}
int cnt(int l, int r) {
	int dw = -1, up = n;
	while (up - dw > 1) {
		int mid = ((up + dw) >> 1);
		if (cl({o[mid], n}, {l, r})) dw = mid;
		else up = mid;
	}
	int st = up;
	dw = st;
	up = n;
	while (up - dw > 1) {
		int mid = ((up + dw) >> 1);
		if (clp({o[mid], n}, {l, r})) dw = mid;
		else up = mid;
	}
//	cout << "asdasd" << up << ' ' << st << endl; // deb
	return up - st;
}


int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	//inp
	cin >> s;
	n = s.size();
	//hs
	tav[0] = 1;
	for (int i = 1; i < MAXN; i++) tav[i] = tav[i - 1] * B % D;
	for (int i = 0; i < n; i++) h[i + 1] = (h[i] * B % D + (s[i] - 'a' + 1)) % D;
	//sa
	auto cmp = [](int i, int j) {
		if (val[i] != val[j]) return val[i] < val[j];
		i += chi;
		j += chi;
		return ((i < n && j < n)? val[i] < val[j]: i > j);
	};
	for (int i = 0; i < n; i++) {
		o[i] = i;
		val[i] = s[i];
	}
	for (chi = 1; tmp[n - 1] != n - 1; chi <<= 1) {
		sort(o, o + n, cmp);//Op
		for (int i = 0; i < n - 1; i++) tmp[i + 1] = tmp[i] + cmp(o[i], o[i + 1]);
		for (int i = 0; i < n; i++) val[o[i]] = tmp[i];
	}
	//zoj
	tool[0] = 0;
	tool[1] = ((s[0] == s[1])? 1: 0);
	if (tool[1]) ans = max(ans, cnt(0, 2));
	for (int i = 2; i < n; i++) {
		tool[i] = max(0ll, min(tool[i - 2], tool[i - 1] - 1));
		if (tool[i] >= tool[i - 1] - 1) while (i + tool[i] < n && i - tool[i] - 1 >= 0 && s[i + tool[i]] == s[i - tool[i] - 1]) {
			tool[i]++;
			ans = max(ans, cnt(i - tool[i], i + tool[i]) * (tool[i] << 1));
		}
	}
	//fard
	tool[0] = 0;
	ans = max(ans, cnt(0, 1));
//	cout << "1 " << ans << endl; // deb
	tool[1] = ((s[0] == s[2])? 1: 0);
	ans = max(ans, cnt(1 - tool[1], 1 + tool[1] + 1));
//	cout << "2 " << ans << endl; // deb
	for (int i = 2; i < n; i++) {
		tool[i] = max(0ll, min(tool[i - 2], tool[i - 1] - 1));
		if (tool[i] >= tool[i - 1] - 1) while (i + tool[i] + 1 < n && i - tool[i] - 1 >= 0 && s[i + tool[i] + 1] == s[i - tool[i] - 1]) {
			tool[i]++;
			ans = max(ans, cnt(i - tool[i], i + tool[i] + 1) * ((tool[i] << 1) | 1));
//			cout << "\\ " << s.substr(i - tool[i], ((tool[i] << 1) | 1)) << ' ' << cnt(i - tool[i], i + tool[i] + 1) << ' ' << ((tool[i] << 1) | 1) << endl; // deb
		}
	}
	//out
	cout << ans;
	return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27