oj.uz

Submission #103293

# Submission time Handle Problem Language Result Execution time Memory
103293 2019-03-29T17:14:01 Z Minnakhmetov Palindromes (APIO14_palindrome) C++14
100 / 100
 855 ms 122824 KB 
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
#pragma warning(disable : 4996)

const int N = 3e5 + 5, L = 20, X = 997, M = 1e9 + 9;
int suf[L][N], cl[L][N], ct[N], pos[N], lcp[N], lb[N], rb[N];
ll h[N], rh[N], p[N];
int n;

bool isPalindrome(int l, int r) {
	ll h1 = h[r + 1] - h[l] * p[r - l + 1] % M,
		h2 = rh[n - l] - rh[n - r - 1] * p[r - l + 1] % M;
	if (h1 < 0)
		h1 += M;
	if (h2 < 0)
		h2 += M;
	return h1 == h2;
}

signed main() {
#ifdef HOME
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	string s;
	cin >> s;

	s.push_back('#');

	n = s.size();

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

	for (int i = 1; i < N; i++)
		ct[i] += ct[i - 1];

	for (int i = n - 1; i >= 0; i--) {
		suf[0][--ct[s[i]]] = i;
	}


	for (int i = 1; i < L; i++) {
		fill(ct, ct + N, 0);
		for (int j = 0; j < n; j++) {
			suf[i - 1][j] -= (1 << (i - 1)) % n;
			if (suf[i - 1][j] < 0)
				suf[i - 1][j] += n;
			ct[cl[i - 1][suf[i - 1][j]]]++;
		}

		for (int i = 1; i < N; i++) {
			ct[i] += ct[i - 1];
		}

		for (int j = n - 1; j >= 0; j--) {
			suf[i][--ct[cl[i - 1][suf[i - 1][j]]]] = suf[i - 1][j];
		}
		for (int j = 0, k = 0; j < n; j++) {
			cl[i][suf[i][j]] = k;
			if (cl[i - 1][suf[i][j]] != cl[i - 1][suf[i][j + 1]] ||
				cl[i - 1][(suf[i][j] + (1 << (i - 1))) % n] !=
				cl[i - 1][(suf[i][j + 1] + (1 << (i - 1))) % n])
				k++;
		}
	}

	for (int i = 0; i < n; i++) {
		pos[suf[L - 1][i]] = i;
	}

	for (int i = 0, k = 0; i < n; i++) {
		int j = pos[i];
		if (j == n - 1) {
			k = 0;
			continue;
		}
		j = suf[L - 1][j + 1];
		while (i + k < n && j + k < n && s[i + k] == s[j + k])
			k++;
		lcp[pos[i]] = k;
		k = max(0, k - 1);
	}


	n--;

	p[0] = 1;
	for (int i = 0; i < n; i++) {
		p[i + 1] = p[i] * X % M;
		h[i + 1] = (h[i] * X + s[i]) % M;
		rh[i + 1] = (rh[i] * X + s[n - 1 - i]) % M;
	}

	vector<vector<int>> ev;

	ll ans = 0;

	for (int i = 0; i < n; i++) {
		int l = 0, r = min(i + 1, n - i);
		while (r - l > 1) {
			int p = (l + r) >> 1;
			if (isPalindrome(i - p, i + p))
				l = p;
			else
				r = p;
		}
		ans = max(ans, l * 2 + 1ll);
		ev.push_back({ i - l, i, 0 });

		if (s[i] == s[i + 1]) {
			l = 0, r = min(i + 1, n - i - 1);
			while (r - l > 1) {
				int p = (l + r) >> 1;
				if (isPalindrome(i - p, i + p + 1))
					l = p;
				else
					r = p;
			}
			ans = max(ans, l * 2 + 2ll);
			ev.push_back({ i - l, i, 1 });
		}
	}

	sort(all(ev));

	vector<int> v;
	for (int i = 1; i <= n; i++) {
		while (!v.empty() && lcp[v.back()] >= lcp[i])
			v.pop_back();
		lb[i] = v.empty() ? 1 : v.back() + 1;
		v.push_back(i);
	}
	v.clear();

	for (int i = n; i > 0; i--) {
		while (!v.empty() && lcp[v.back()] >= lcp[i])
			v.pop_back();
		rb[i] = v.empty() ? n - 1 : v.back();
		v.push_back(i);
	}

	set<int> st[2];
	for (int i = 0, j = 0; i < n; i++) {
		while (j < ev.size() && ev[j][0] == i) {
			st[ev[j][2]].insert(ev[j][1]);
			j++;
		}
		int k = pos[i], r = i + lcp[k] - 1;
		if (lcp[k] > 0) {
			auto it = st[0].upper_bound((r - i) / 2 + i);
			if (it != st[0].begin()) {
				it--;
				ll len = (*it - i) * 2 + 1;
				ans = max(ans, (rb[k] - lb[k] + 1) * len);
			}
		}
		if (lcp[k] > 1) {
			auto it = st[1].upper_bound((r - i - 1) / 2 + i);
			if (it != st[1].begin()) {
				it--;
				ll len = (*it - i) * 2 + 2;
				ans = max(ans, (rb[k] - lb[k] + 1) * len);
			}
		}
	}

	cout << ans;

	return 0;
}

Compilation message

palindrome.cpp:41:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable : 4996)
 
palindrome.cpp: In function 'int main()':
palindrome.cpp:74:10: warning: array subscript has type 'char' [-Wchar-subscripts]
   ct[s[i]]++;
          ^
palindrome.cpp:82:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   suf[0][--ct[s[i]]] = i;
                   ^
palindrome.cpp:188:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (j < ev.size() && ev[j][0] == i) {
          ~~^~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1920 KB Output is correct
2 Correct 21 ms 1792 KB Output is correct
3 Correct 20 ms 1792 KB Output is correct
4 Correct 20 ms 1792 KB Output is correct
5 Correct 20 ms 1792 KB Output is correct
6 Correct 21 ms 1792 KB Output is correct
7 Correct 19 ms 1792 KB Output is correct
8 Correct 22 ms 1792 KB Output is correct
9 Correct 22 ms 1920 KB Output is correct
10 Correct 18 ms 1792 KB Output is correct
11 Correct 22 ms 1792 KB Output is correct
12 Correct 19 ms 1784 KB Output is correct
13 Correct 23 ms 1792 KB Output is correct
14 Correct 20 ms 1920 KB Output is correct
15 Correct 23 ms 1784 KB Output is correct
16 Correct 23 ms 1792 KB Output is correct
17 Correct 20 ms 1792 KB Output is correct
18 Correct 23 ms 1920 KB Output is correct
19 Correct 22 ms 1792 KB Output is correct
20 Correct 24 ms 1792 KB Output is correct
21 Correct 14 ms 1792 KB Output is correct
22 Correct 20 ms 1792 KB Output is correct
23 Correct 21 ms 1920 KB Output is correct
24 Correct 22 ms 1784 KB Output is correct
25 Correct 22 ms 1792 KB Output is correct
26 Correct 22 ms 1792 KB Output is correct
27 Correct 19 ms 1792 KB Output is correct
28 Correct 20 ms 1920 KB Output is correct
29 Correct 20 ms 1792 KB Output is correct
30 Correct 19 ms 1784 KB Output is correct
31 Correct 21 ms 1912 KB Output is correct
32 Correct 19 ms 1792 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2168 KB Output is correct
2 Correct 21 ms 2176 KB Output is correct
3 Correct 27 ms 2304 KB Output is correct
4 Correct 21 ms 2176 KB Output is correct
5 Correct 21 ms 2176 KB Output is correct
6 Correct 21 ms 2168 KB Output is correct
7 Correct 21 ms 2176 KB Output is correct
8 Correct 22 ms 2176 KB Output is correct
9 Correct 22 ms 2168 KB Output is correct
10 Correct 21 ms 2176 KB Output is correct
11 Correct 30 ms 2304 KB Output is correct
12 Correct 21 ms 2164 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 4896 KB Output is correct
2 Correct 31 ms 4916 KB Output is correct
3 Correct 35 ms 5936 KB Output is correct
4 Correct 35 ms 5936 KB Output is correct
5 Correct 34 ms 4788 KB Output is correct
6 Correct 32 ms 4916 KB Output is correct
7 Correct 39 ms 5020 KB Output is correct
8 Correct 30 ms 4916 KB Output is correct
9 Correct 32 ms 4788 KB Output is correct
10 Correct 36 ms 5172 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 31880 KB Output is correct
2 Correct 155 ms 31776 KB Output is correct
3 Correct 257 ms 42324 KB Output is correct
4 Correct 261 ms 42040 KB Output is correct
5 Correct 202 ms 31620 KB Output is correct
6 Correct 186 ms 31644 KB Output is correct
7 Correct 218 ms 36760 KB Output is correct
8 Correct 186 ms 32036 KB Output is correct
9 Correct 192 ms 34340 KB Output is correct
10 Correct 192 ms 35096 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 91708 KB Output is correct
2 Correct 460 ms 91324 KB Output is correct
3 Correct 855 ms 122824 KB Output is correct
4 Correct 775 ms 122124 KB Output is correct
5 Correct 516 ms 91388 KB Output is correct
6 Correct 607 ms 99928 KB Output is correct
7 Correct 729 ms 105092 KB Output is correct
8 Correct 741 ms 92396 KB Output is correct
9 Correct 664 ms 92376 KB Output is correct
10 Correct 699 ms 101276 KB Output is correct
11 Correct 600 ms 91676 KB Output is correct
12 Correct 756 ms 95576 KB Output is correct