oj.uz

Submission #102780

# Submission time Handle Problem Language Result Execution time Memory
102780 2019-03-27T13:25:37 Z Minnakhmetov Palindromes (APIO14_palindrome) C++14
0 / 100
 862 ms 123300 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;
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],
		h2 = rh[n - l] - rh[n - r - 1] * p[r - l + 1];
	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;
		h[i + 1] = h[i] * X + s[i];
		rh[i + 1] = rh[i] * X + s[n - 1 - i];
	}

	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];
		if (lcp[k] != 0) {
			int r = i + lcp[k] - 1;
			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);
			}
			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:70:10: warning: array subscript has type 'char' [-Wchar-subscripts]
   ct[s[i]]++;
          ^
palindrome.cpp:78:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   suf[0][--ct[s[i]]] = i;
                   ^
palindrome.cpp:184:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (j < ev.size() && ev[j][0] == i) {
          ~~^~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1792 KB Output is correct
2 Correct 20 ms 1792 KB Output is correct
3 Correct 19 ms 1792 KB Output is correct
4 Correct 19 ms 1792 KB Output is correct
5 Correct 20 ms 1920 KB Output is correct
6 Correct 19 ms 1792 KB Output is correct
7 Correct 22 ms 1792 KB Output is correct
8 Incorrect 21 ms 1792 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2176 KB Output is correct
2 Correct 24 ms 2048 KB Output is correct
3 Correct 22 ms 2168 KB Output is correct
4 Correct 24 ms 2040 KB Output is correct
5 Correct 23 ms 2168 KB Output is correct
6 Correct 24 ms 2168 KB Output is correct
7 Correct 23 ms 2048 KB Output is correct
8 Correct 23 ms 2176 KB Output is correct
9 Correct 21 ms 2172 KB Output is correct
10 Incorrect 20 ms 2176 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4888 KB Output is correct
2 Correct 26 ms 4788 KB Output is correct
3 Correct 37 ms 5816 KB Output is correct
4 Correct 35 ms 5808 KB Output is correct
5 Correct 28 ms 4788 KB Output is correct
6 Correct 29 ms 4924 KB Output is correct
7 Correct 32 ms 4796 KB Output is correct
8 Incorrect 28 ms 4796 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 31920 KB Output is correct
2 Correct 135 ms 31908 KB Output is correct
3 Correct 240 ms 42472 KB Output is correct
4 Correct 240 ms 42264 KB Output is correct
5 Correct 146 ms 31908 KB Output is correct
6 Correct 138 ms 31780 KB Output is correct
7 Correct 169 ms 36900 KB Output is correct
8 Incorrect 194 ms 32188 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 92076 KB Output is correct
2 Correct 456 ms 91612 KB Output is correct
3 Correct 862 ms 123300 KB Output is correct
4 Correct 736 ms 122484 KB Output is correct
5 Correct 523 ms 91480 KB Output is correct
6 Correct 619 ms 100184 KB Output is correct
7 Correct 623 ms 105304 KB Output is correct
8 Incorrect 605 ms 92636 KB Output isn't correct
9 Halted 0 ms 0 KB -