oj.uz

Submission #103291

# Submission time Handle Problem Language Result Execution time Memory
103291 2019-03-29T17:08:46 Z Minnakhmetov Palindromes (APIO14_palindrome) C++14
73 / 100
 1000 ms 128180 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;
string s;


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



//bool isPalindrome2(string s) {
//	for (int i = 0; i < s.size() / 2; i++) {
//		if (s[i] != *(s.end() - 1 - i))
//			return false;
//	}
//	return true;
//}
//
//ll brute() {
//	ll ans = 0;
//	map<string, int> mp;
//	for (int i = 0; i < n; i++) {
//		for (int j = i; j < n; j++) {
//			mp[s.substr(i, j - i + 1)]++;
//		}
//	}
//	for (auto &p : mp) {
//		if (isPalindrome2(p.first))
//			ans = max(ans, p.first.size() * (ll)p.second);
//	}
//	return ans;
//}

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

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


	//cout << "\n" << brute();

	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:100:10: warning: array subscript has type 'char' [-Wchar-subscripts]
   ct[s[i]]++;
          ^
palindrome.cpp:108:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   suf[0][--ct[s[i]]] = i;
                   ^
palindrome.cpp:215: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 20 ms 1792 KB Output is correct
2 Correct 20 ms 1792 KB Output is correct
3 Correct 21 ms 1792 KB Output is correct
4 Correct 19 ms 1792 KB Output is correct
5 Correct 21 ms 1792 KB Output is correct
6 Correct 21 ms 1792 KB Output is correct
7 Correct 23 ms 1792 KB Output is correct
8 Correct 19 ms 1792 KB Output is correct
9 Correct 20 ms 1792 KB Output is correct
10 Correct 21 ms 1912 KB Output is correct
11 Correct 18 ms 1920 KB Output is correct
12 Correct 19 ms 1792 KB Output is correct
13 Correct 19 ms 1920 KB Output is correct
14 Correct 20 ms 1792 KB Output is correct
15 Correct 21 ms 1784 KB Output is correct
16 Correct 24 ms 1784 KB Output is correct
17 Correct 22 ms 1792 KB Output is correct
18 Correct 22 ms 1784 KB Output is correct
19 Correct 23 ms 1792 KB Output is correct
20 Correct 21 ms 1920 KB Output is correct
21 Correct 32 ms 1916 KB Output is correct
22 Correct 23 ms 1792 KB Output is correct
23 Correct 20 ms 1912 KB Output is correct
24 Correct 24 ms 1920 KB Output is correct
25 Correct 21 ms 1920 KB Output is correct
26 Correct 21 ms 1920 KB Output is correct
27 Correct 20 ms 1912 KB Output is correct
28 Correct 20 ms 1920 KB Output is correct
29 Correct 20 ms 1920 KB Output is correct
30 Correct 21 ms 1792 KB Output is correct
31 Correct 22 ms 1912 KB Output is correct
32 Correct 23 ms 1920 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2176 KB Output is correct
2 Correct 20 ms 2176 KB Output is correct
3 Correct 23 ms 2296 KB Output is correct
4 Correct 23 ms 2168 KB Output is correct
5 Correct 22 ms 2304 KB Output is correct
6 Correct 24 ms 2304 KB Output is correct
7 Correct 20 ms 2168 KB Output is correct
8 Correct 23 ms 2296 KB Output is correct
9 Correct 20 ms 2160 KB Output is correct
10 Correct 20 ms 2168 KB Output is correct
11 Correct 19 ms 2212 KB Output is correct
12 Correct 21 ms 2176 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 5248 KB Output is correct
2 Correct 32 ms 5144 KB Output is correct
3 Correct 48 ms 6156 KB Output is correct
4 Correct 46 ms 6064 KB Output is correct
5 Correct 35 ms 5016 KB Output is correct
6 Correct 36 ms 5300 KB Output is correct
7 Correct 35 ms 5300 KB Output is correct
8 Correct 35 ms 5172 KB Output is correct
9 Correct 36 ms 5300 KB Output is correct
10 Correct 38 ms 5560 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 34324 KB Output is correct
2 Correct 212 ms 34340 KB Output is correct
3 Correct 335 ms 44716 KB Output is correct
4 Correct 312 ms 44568 KB Output is correct
5 Correct 205 ms 34080 KB Output is correct
6 Correct 212 ms 34180 KB Output is correct
7 Correct 230 ms 39208 KB Output is correct
8 Correct 195 ms 34572 KB Output is correct
9 Correct 205 ms 36772 KB Output is correct
10 Correct 235 ms 37556 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 98984 KB Output is correct
2 Correct 595 ms 98680 KB Output is correct
3 Execution timed out 1076 ms 128180 KB Time limit exceeded
4 Halted 0 ms 0 KB -