oj.uz

Submission #670227

# Submission time Handle Problem Language Result Execution time Memory
670227 2022-12-08T10:37:00 Z Radin_Zahedi2 Palindromes (APIO14_palindrome) C++17
0 / 100
 1000 ms 30132 KB 
#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;
string s;
const int N = 3e5 + 5;
int hashed[N];
int hsahed[N];
int po[N];

int a[N];
int cl[N];
int lcp[N];

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


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 crehash() {
	po[0] = 1;
	for (int i = 1; i <= n; i++) {
		po[i] = mull(po[i - 1], p);
	}

	hashed[0] = (int)s[0];
	for (int i = 1; i < n; i++) {
		hashed[i] = mull(hashed[i - 1], p);
		hashed[i] += (int)s[i];
	}

	hsahed[n - 1] = (int)s[n - 1];
	for (int i = n - 2; i >= 0; i--) {
		hsahed[i] = mull(hsahed[i + 1], p);
		hsahed[i] += (int)s[i];
	}
}

bool palin(int l, int r) {
	int val;
	if (l == 0) {
		val = hashed[r];
	}
	else {
		val = hashed[r] - mull(po[r - l + 1], hashed[l - 1]);
		val += mod;
		val %= mod;
	}

	int lav;
	if (r == n - 1) {
		lav = hsahed[l];
	}
	else {
		lav = hsahed[l] - mull(po[r - l + 1], hsahed[r + 1]);
		lav += mod;
		lav %= mod;
	}

	bool ok = true;
	for (int i = 0; l + i < r - i; i++) {
		if (s[l + i] != s[r - i]) {
			ok = false;
		}
	}

	if (ok != (val == lav)) {
		throw;
	}

	return (val == lav);
}

void init() {
}

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

	n++;
	s += '$';
}

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

	crehash();

	for (int i = 0; i < n; i++) {
		par[i] = i;
		len[i] = 1;
	}

	vector<pair<int, int>> edges;
	for (int i = 1; i < n; i++) {
		edges.pb(mp(lcp[i], i));
	}

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

	ll ans = 0;

	if (palin(0, n - 2)) {
		ans = n - 1;
	}
	for (int i = 0; i < n - 1; i++) {
		int ind = edges[i].se;

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

		if (palin(a[ind], a[ind] + lcp[ind] - 1)) {
			ans = max(ans, 1ll * lcp[ind] * (len[p1] + len[p2]));
		}

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

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

			len[p1] += len[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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 0 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 1 ms 468 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1248 KB Output is correct
2 Correct 15 ms 1256 KB Output is correct
3 Correct 21 ms 1364 KB Output is correct
4 Correct 17 ms 1228 KB Output is correct
5 Correct 13 ms 1364 KB Output is correct
6 Correct 12 ms 1380 KB Output is correct
7 Correct 10 ms 1364 KB Output is correct
8 Runtime error 13 ms 2488 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 8868 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 30132 KB Time limit exceeded
2 Halted 0 ms 0 KB -