oj.uz

Submission #36593

# Submission time Handle Problem Language Result Execution time Memory
36593 2017-12-11T17:02:12 Z cheater2k Palindromes (APIO14_palindrome) C++14
15 / 100
 456 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 300005;
string s, t;
int n; // size of s

//--------------------------------------------------------------------------------
struct SuffixArray {
	typedef pair<int,int> ii;
	typedef pair<ii, int> II;
	int sa[N];
	int lcp[N];
	int p[N][19];

	// for sorting
	ii A[N];
	II AA[N];
	vector<II> srt[N];
	// ---------------------------------------------------------------------------------------

	void buildSA() {
		int cnt;
		// sort the first character
		ii A[N];
		for (int i = 1; i <= n; ++i) A[i] = make_pair(s[i], i);
		sort(A + 1, A + n + 1);
		cnt = 0;
		for (int i = 1; i <= n; ++i) 
			p[A[i].second][0] = (i == 1 || (i > 1 && A[i].first != A[i-1].first)) ? ++cnt : cnt;
		
		// build Suffix Array using counting sort
		for (int k = 1; k < 19; ++k) {
			for (int i = 1; i <= n; ++i) {
				AA[i] = make_pair(ii(p[i][k-1], (i + (1 << k-1) <= n) ? p[i + (1 << k-1)][k-1] : 0), i);
			}
			// sort by second part
			for (int i = 1; i <= n; ++i) srt[AA[i].first.second].push_back(AA[i]); // second part
			cnt = 0;
			for (int i = 0; i <= n; ++i) {
				while(srt[i].size()) AA[++cnt] = srt[i].back(), srt[i].pop_back();	
			}
			// sort by first part
			for (int i = 1; i <= n; ++i) srt[AA[i].first.first].push_back(AA[i]); // first part
			cnt = 0;
			for (int i = 0; i <= n; ++i) {
				reverse(srt[i].begin(), srt[i].end());
				while(srt[i].size()) AA[++cnt] = srt[i].back(), srt[i].pop_back();
			}
			// restore p[][k]
			cnt = 0;
			for (int i = 1; i <= n; ++i)
				p[AA[i].second][k] = (i == 1 || (i > 1 && AA[i].first != AA[i-1].first)) ? ++cnt : cnt;
		}

		// sa
		for (int i = 1; i <= n; ++i) sa[p[i][18]] = i;
	}

	int getLCP(int x, int y) {
		int ret = 0;
		for (int i = 18; i >= 0; --i) {
			if (x + (1 << i) - 1 <= n && y + (1 << i) - 1 <= n && p[x][i] == p[y][i]) {
				x += (1 << i); y += (1 << i); ret += (1 << i);
			}
		}
		return ret;
	}

	void buildLCP() {
		// lcp[i] (1 <= i < n) is the longest common prefix of sa[i] and sa[i+1]
		for (int i = 1; i < n; ++i) {
			lcp[i] = getLCP(sa[i], sa[i+1]);
		}
		lcp[n] = 0;
	}
} sa;

// -------------------------------------------------------------------------------
int to[N * 2]; // for Manacher
void manacher() {
	int n2 = 2 * n + 1;
	string t = string(n2, '.');
	for (int i = 1; i < n2; i += 2) t[i] = s[(i - 1) / 2];

	int c = 0, r = 0;
	for (int i = 1; i < n2-1; ++i) {
		int i_mirror = 2 * c - i; // i' = c - (i - c)
		to[i] = (r > i) ? min(r - i, to[i_mirror]) : 0;
		// attempt to expand palindrome centered at i
		while(i + 1 + to[i] < n2 && i - 1 - to[i] >= 0 && t[i + 1 + to[i]] == t[i - 1 - to[i]]) ++to[i];
		if (i + to[i] > r) { // update c and r
			c = i;
			r = i + to[i];
		}
	}
}
// -------------------------------------------------------------------------------
int len[N]; // len[i] is the longest palindrome centered at i
int a[N]; // new lcp[]
int l[N], r[N];
long long ans;
void solve(int x) { 
	// x = 0: even
	// x = 1: odd
	for (int i = 1; i <= n; ++i) {
		if (x == 0) { // even
			len[i] = to[2 * i - 2] / 2;
		} else { // odd
			len[i] = (to[2 * i - 1] + 1) / 2;
		}
	}

	// replace lcp[] with a[]
	for (int i = 1; i < n; ++i) {
		a[i] = min(sa.lcp[i], min(len[sa.sa[i]], len[sa.sa[i + 1]]));
	}

	// KAGAIN
	for (int i = 1; i <= n; ++i) {
		l[i] = i;
		while(l[i] > 1 && a[i] <= a[l[i] - 1]) l[i] = l[l[i] - 1];
	}
	for (int i = n; i >= 1; --i) {
		r[i] = i;
		while(r[i] < n && a[i] <= a[r[i] + 1]) r[i] = r[r[i] + 1];
	}
	for (int i = 1; i <= n; ++i) {
		ans = max(ans, 1LL * (a[i] * 2 - x) * (r[i] - l[i] + 2)); // real_len = a[i] * 2 - x
	}
	for (int i = 1; i <= n; ++i) {
		ans = max(ans, (long long)len[i] * 2 - x);
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> s;
	n = s.size();
	manacher();
	s = ' ' + s;
	sa.buildSA();
	sa.buildLCP();

	solve(1);
	solve(0);

	cout << ans << endl;
}

Compilation message

palindrome.cpp: In member function 'void SuffixArray::buildSA()':
palindrome.cpp:35:49: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
     AA[i] = make_pair(ii(p[i][k-1], (i + (1 << k-1) <= n) ? p[i + (1 << k-1)][k-1] : 0), i);
                                                 ^
palindrome.cpp:35:74: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
     AA[i] = make_pair(ii(p[i][k-1], (i + (1 << k-1) <= n) ? p[i + (1 << k-1)][k-1] : 0), i);
                                                                          ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 48936 KB Output is correct
2 Correct 0 ms 48928 KB Output is correct
3 Correct 3 ms 48932 KB Output is correct
4 Correct 3 ms 48936 KB Output is correct
5 Correct 0 ms 48932 KB Output is correct
6 Correct 6 ms 48936 KB Output is correct
7 Correct 9 ms 48932 KB Output is correct
8 Correct 0 ms 48932 KB Output is correct
9 Correct 3 ms 48928 KB Output is correct
10 Incorrect 3 ms 48932 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 0 ms 49068 KB Output is correct
2 Correct 3 ms 49068 KB Output is correct
3 Correct 3 ms 49068 KB Output is correct
4 Correct 6 ms 49060 KB Output is correct
5 Correct 0 ms 49068 KB Output is correct
6 Correct 3 ms 49064 KB Output is correct
7 Correct 0 ms 49068 KB Output is correct
8 Correct 0 ms 49064 KB Output is correct
9 Correct 3 ms 49068 KB Output is correct
10 Correct 0 ms 48932 KB Output is correct
11 Correct 3 ms 48932 KB Output is correct
12 Correct 0 ms 49068 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 51600 KB Output is correct
2 Correct 9 ms 50376 KB Output is correct
3 Correct 19 ms 51888 KB Output is correct
4 Correct 6 ms 51564 KB Output is correct
5 Correct 19 ms 50984 KB Output is correct
6 Correct 9 ms 50524 KB Output is correct
7 Correct 6 ms 50776 KB Output is correct
8 Correct 16 ms 49980 KB Output is correct
9 Correct 16 ms 49972 KB Output is correct
10 Incorrect 13 ms 50664 KB Output isn't correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 77708 KB Output is correct
2 Correct 123 ms 71744 KB Output is correct
3 Correct 106 ms 79592 KB Output is correct
4 Correct 119 ms 76068 KB Output is correct
5 Correct 273 ms 69856 KB Output is correct
6 Correct 256 ms 74848 KB Output is correct
7 Correct 176 ms 74144 KB Output is correct
8 Correct 313 ms 57668 KB Output is correct
9 Correct 279 ms 62252 KB Output is correct
10 Incorrect 263 ms 71836 KB Output isn't correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 111404 KB Output is correct
2 Memory limit exceeded 386 ms 131072 KB Memory limit exceeded
3 Halted 0 ms 0 KB -