Submission #670244

#	Time	Username	Problem	Language	Result	Execution time	Memory
670244		Radin_Zahedi2	Palindromes (APIO14_palindrome)	C++17	0 / 100	593 ms	52816 KiB

palindrome

#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)x.size()
#define endl '\n'
const int mod = 1e9 + 7;
const int p = 2;
const int inf = 2e9 + 5;
const ll linf = 9e18 + 5;


int n;
int ini;
string s;
const int N = 6e5 + 5;
int a[N];
int cl[N];
int lcp[N];

int par[N];
int len[N];
int val[N];

bool cmp(int x, int y) {
	if (lcp[x] < lcp[y]) {
		return false;
	}
	if (lcp[x] > lcp[y]) {
		return true;
	}

	bool diffa = (a[x - 1] < ini) ^ (a[x] < ini);
	bool diffb = (a[y - 1] < ini) ^ (a[y] < ini);

	return diffa < diffb;
}

int mull(int a, int b) {
	return (1ll * a * b) % mod;
}

void cntsort() {
	vector<int> have[n];

	for (int i = 0; i < n; i++) {
		have[cl[a[i]]].pb(a[i]);
	}

	int ind = 0;
	for (int i = 0; i < n; i++) {
		for (auto x : have[i]) {
			a[ind] = x;
			ind++;
		}
	}
}

void cresuff() {
	pair<char, int> arr[n];
	for (int i = 0; i < n; i++) {
		arr[i] = mp(s[i], i);
	}
	sort(arr + 0, arr + n);

	a[0] = arr[0].se;
	cl[a[0]] = 0;
	for (int i = 1; i < n; i++) {
		a[i] = arr[i].se;

		if (arr[i].fi == arr[i - 1].fi) {
			cl[a[i]] = cl[a[i - 1]];
		}
		else {
			cl[a[i]] = cl[a[i - 1]] + 1;
		}
	}


	int len = 1;
	while (len < n) {
		for (int i = 0; i < n; i++) {
			a[i] -= len;
			a[i] += n;
			a[i] %= n;
		}

		cntsort();

		int cl2[n];

		cl2[a[0]] = 0;
		for (int i = 1; i < n; i++) {
			pair<int, int> pre = mp(cl[a[i - 1]], cl[(a[i - 1] + len) % n]);
			pair<int, int> now = mp(cl[a[i]], cl[(a[i] + len) % n]);

			if (pre == now) {
				cl2[a[i]] = cl2[a[i - 1]];
			}
			else {
				cl2[a[i]] = cl2[a[i - 1]] + 1;
			}
		}

		for (int i = 0; i < n; i++) {
			cl[i] = cl2[i];
		}

		len <<= 1;
	}
}

void crelcp() {
	int have = 0;

	for (int i = 0; i < n - 1; i++) {
		int ind = cl[i];

		while (i + have < n && a[ind - 1] + have < n) {
			if (s[i + have] != s[a[ind - 1] + have]) {
				break;
			}

			have++;
		}

		lcp[ind] = have;

		have = max(0, have - 1);
	}
}

void init() {
}

void input() {
	cin >> s;
	n = sz(s);

	ini = n;

	string t = s;
	reverse(t.begin(), t.end());
	s = s + '$' + t + '\0';
	n = sz(s);
}

void solve() {
	cresuff();
	crelcp();

	for (int i = 0; i < n; i++) {
		par[i] = i;
		len[i] = 1;
		val[i] = (a[i] < ini);
//		cout << i << ' ' << s.substr(a[i]) << ' ' << lcp[i] << ' ' << val[i] << endl;
	}

	vector<int> edges;
	for (int i = 1; i < n; i++) {
		edges.pb(i);
	}

	sort(edges.begin(), edges.end(), cmp);

	ll ans = 0;

	for (int i = 0; i < n - 1; i++) {
		int ind = edges[i];

		int p1 = par[ind - 1];
		int p2 = par[ind];

//		cout << ind << ' ' << lcp[ind] << ' ' << (a[ind - 1]) << ' ' << (a[ind]) << endl;
		if (lcp[ind]) {
			if ((a[ind - 1] < ini) ^ (a[ind] < ini)) {
				int i1 = a[ind - 1];
				int i2 = a[ind];

				if (i1 >= ini) {
					i1 = 2 * ini - i1;
				}
				if (i2 >= ini) {
					i2 = 2 * ini - i2;
				}

				int dist = abs(i1 - i2) + 1;
//				cout << "	" << i1 << ' ' << i2 << ' ' << val[p1] << ' ' << val[p2] << ' ' << min(dist, lcp[ind]) * (val[p1] + val[p2]) << endl;
				if (lcp[ind] >= dist) {
					ans = max(ans, 1ll * min(dist, lcp[ind]) * (val[p1] + val[p2]));
				}
			}
		}

		if (len[p1] < len[p2]) {	
			for (int i = ind - len[p1]; i < ind; i++) {
				par[i] = p2;
			}

			len[p2] += len[p1];
			val[p2] += val[p1];
		}
		else {
			for (int i = ind; i < ind + len[p2]; i++) {
				par[i] = p1;
			}

			len[p1] += len[p2];
			val[p1] += val[p2];
		}
	}

	cout << ans;
}

void output() {
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int number_of_testcases = 1;
	//cin >> number_of_testcases;
	while (number_of_testcases--) {
		init();

		input();

		solve();

		output();
	}

	return 0;
}

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