oj.uz

Submission #88927

# Submission time Handle Problem Language Result Execution time Memory
88927 2018-12-09T23:23:01 Z Anai Palindromes (APIO14_palindrome) C++11
15 / 100
 1000 ms 3348 KB 
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

using i64 = long long;
using pii = pair<int, int>;

const int N = 6e5 + 5, LG = 20;

int pal[N], sa[LG][N];
char str[N];

vector<int> sorted;
int n;

static void add_stars() {
	char tmp[N];
	n = 0;
	for (int i = 1; str[i]; ++i) {
		tmp[2 * i - 1] = '*';
		tmp[2 * i] = str[i];
		n+= 2; }
	tmp[n + 1] = '*';
	tmp[n + 2] = 0;
	strcpy(str + 1, tmp + 1); }

static void manacher() {
	int mid, r;

	str[n + 1] = '$';
	str[0] = '#';
	r = -1;

	for (int i = 1; i <= n; ++i) {
		pal[i] = 1;
		if (i > r) {
			while (str[i - pal[i]] == str[i + pal[i]])
				pal[i]+= 1;
			mid = i;
			r = mid + pal[i] - 1; }
		else {
			pal[i] = min(r - i + 1, pal[mid - (i - mid)]);
			while (str[i - pal[i]] == str[i + pal[i]])
				pal[i]+= 1; } } }

static void build_sa() {
	pii lst;
	int ptr;

	sorted.resize(n);
	iota(begin(sorted), end(sorted), 1);
	for (int i = 1; i <= n; ++i)
		sa[0][i] = str[i];

	for (int lg = 1; lg < LG; ++lg) {
		function<pii(int)> sa_pair = [&](int p) {
			return pii(sa[lg - 1][p], p + (1 << lg - 1) <= n ? sa[lg - 1][p + (1 << lg - 1)] : 0); };

		sort(begin(sorted), end(sorted), [&](const int &a, const int &b) {
			return sa_pair(a) < sa_pair(b); });

		lst = {-1, -1};
		ptr = 0;
		for (auto i: sorted) {
			if (sa_pair(i) != lst)
				++ptr;
			sa[lg][i] = ptr;
			lst = sa_pair(i); } } }

static int lcp(int a, int b) {
	if (str[a] != str[b])
		return 0;
	int len = 0, ant = min(pal[a], pal[b]);
	bool flag = ('a' <= str[a] && str[a] <= 'z');

	for (int lg = LG - 1; lg >= 0; --lg)
		if (sa[lg][a] == sa[lg][b]) {
			a+= 1 << lg;
			b+= 1 << lg;
			len+= 1 << lg; }

	return 2 * min(len / 2, ant / 2) - int(flag); }

static i64 skyline() {
	vector<int> stk, st, dr, val;
	int tsiz = sorted.size();
	i64 ant = 0;

	for (auto i: sorted)
		ant = max(ant, pal[i] - 1LL);

	tsiz = sorted.size();
	for (auto &v: {&st, &dr, &val, &stk})
		v->reserve(tsiz);
	for (int i = 1; i < tsiz; ++i)
		val.push_back(lcp(sorted[i - 1], sorted[i]));

	for (int i = 0; i < val.size(); ++i) {
		while (!stk.empty() && val[stk.back()] >= val[i])
			stk.pop_back();
		st.push_back(stk.empty() ? 0 : stk.back() + 1);
		stk.push_back(i); }
	stk.clear();
	for (int i = val.size() - 1; i >= 0; --i) {
		while (!stk.empty() && val[stk.back()] >= val[i])
			stk.pop_back();
		dr.push_back(stk.empty() ? tsiz - 2 : stk.back() - 1);
		stk.push_back(i); }
	reverse(begin(dr), end(dr));

	for (int i = 0; i < tsiz - 1; ++i)
		ant = max(ant, i64(dr[i] - st[i] + 2) * val[i]);

	return ant; }

int main() {
#ifdef HOME
	freopen("apio_palindromes.in", "r", stdin);
	freopen("apio_palindromes.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> (str + 1);

	add_stars();
	n = strlen(str + 1);
	manacher();
	build_sa();

	cout << skyline() << endl;

	return 0; }

Compilation message

palindrome.cpp: In lambda function:
palindrome.cpp:58:43: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
    return pii(sa[lg - 1][p], p + (1 << lg - 1) <= n ? sa[lg - 1][p + (1 << lg - 1)] : 0); };
                                        ~~~^~~
palindrome.cpp:58:79: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
    return pii(sa[lg - 1][p], p + (1 << lg - 1) <= n ? sa[lg - 1][p + (1 << lg - 1)] : 0); };
                                                                            ~~~^~~
palindrome.cpp: In function 'i64 skyline()':
palindrome.cpp:99:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < val.size(); ++i) {
                  ~~^~~~~~~~~~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:43:36: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
    pal[i] = min(r - i + 1, pal[mid - (i - mid)]);
                                ~~~~^~~~~~~~~~~
palindrome.cpp:29:6: note: 'mid' was declared here
  int mid, r;
      ^~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 2 ms 688 KB Output is correct
10 Incorrect 2 ms 688 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 928 KB Output is correct
2 Correct 7 ms 928 KB Output is correct
3 Correct 7 ms 1052 KB Output is correct
4 Correct 7 ms 1060 KB Output is correct
5 Correct 7 ms 1064 KB Output is correct
6 Correct 7 ms 1064 KB Output is correct
7 Correct 7 ms 1072 KB Output is correct
8 Correct 7 ms 1120 KB Output is correct
9 Correct 7 ms 1124 KB Output is correct
10 Correct 8 ms 1128 KB Output is correct
11 Correct 8 ms 1260 KB Output is correct
12 Correct 8 ms 1260 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 3056 KB Output is correct
2 Correct 71 ms 3056 KB Output is correct
3 Correct 96 ms 3076 KB Output is correct
4 Correct 83 ms 3088 KB Output is correct
5 Correct 72 ms 3204 KB Output is correct
6 Correct 73 ms 3204 KB Output is correct
7 Correct 67 ms 3348 KB Output is correct
8 Correct 82 ms 3348 KB Output is correct
9 Correct 82 ms 3348 KB Output is correct
10 Incorrect 75 ms 3348 KB Output isn't correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1062 ms 3348 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 1064 ms 3348 KB Time limit exceeded
2 Halted 0 ms 0 KB -