oj.uz

Submission #102783

# Submission time Handle Problem Language Result Execution time Memory
102783 2019-03-27T13:29:31 Z Minnakhmetov Palindromes (APIO14_palindrome) C++14
0 / 100
 1000 ms 129952 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[2] = { 997, 883 }, M[2] = { (int)1e9 + 7, (int)1e9 + 9 };
int suf[L][N], cl[L][N], ct[N], pos[N], lcp[N], lb[N], rb[N];
ll h[2][N], rh[2][N], p[2][N];
int n; 

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

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--;

	for (int j = 0; j < 2; j++) {
		p[j][0] = 1;
		for (int i = 0; i < n; i++) {
			p[j][i + 1] = p[j][i] * X[j] % M[j];
			h[j][i + 1] = (h[j][i] * X[j] + s[i]) % M[j];
			rh[j][i + 1] = (rh[j][i] * X[j] + s[n - 1 - i]) % M[j];
		}
	}
	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: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:189: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 20 ms 1792 KB Output is correct
2 Correct 22 ms 1936 KB Output is correct
3 Correct 21 ms 1784 KB Output is correct
4 Correct 20 ms 1784 KB Output is correct
5 Correct 22 ms 1792 KB Output is correct
6 Correct 23 ms 1884 KB Output is correct
7 Correct 22 ms 1912 KB Output is correct
8 Incorrect 19 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 22 ms 2168 KB Output is correct
3 Correct 21 ms 2304 KB Output is correct
4 Correct 24 ms 2176 KB Output is correct
5 Correct 23 ms 2304 KB Output is correct
6 Correct 21 ms 2304 KB Output is correct
7 Correct 22 ms 2176 KB Output is correct
8 Correct 22 ms 2116 KB Output is correct
9 Correct 21 ms 2176 KB Output is correct
10 Incorrect 21 ms 2168 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5044 KB Output is correct
2 Correct 29 ms 5052 KB Output is correct
3 Correct 42 ms 6068 KB Output is correct
4 Correct 38 ms 6192 KB Output is correct
5 Correct 37 ms 5052 KB Output is correct
6 Correct 39 ms 5300 KB Output is correct
7 Correct 30 ms 5180 KB Output is correct
8 Incorrect 34 ms 5180 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 34200 KB Output is correct
2 Correct 190 ms 34344 KB Output is correct
3 Correct 302 ms 44608 KB Output is correct
4 Correct 279 ms 44468 KB Output is correct
5 Correct 173 ms 34084 KB Output is correct
6 Correct 214 ms 34080 KB Output is correct
7 Correct 244 ms 39192 KB Output is correct
8 Incorrect 199 ms 34468 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 667 ms 98688 KB Output is correct
2 Correct 548 ms 98268 KB Output is correct
3 Execution timed out 1034 ms 129952 KB Time limit exceeded
4 Halted 0 ms 0 KB -