oj.uz

Submission #265561

# Submission time Handle Problem Language Result Execution time Memory
265561 2020-08-15T01:26:53 Z square1001 Palindromes (APIO14_palindrome) C++14
47 / 100
 1000 ms 79200 KB 
// APIO 2014 Problem 1 - Palindromes

#include <tuple>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
#include <unordered_set>
using namespace std;
int N; unordered_set<int> s1[600009], s2[600009];
tuple<long long, int, int, int> solve(int l, int r, vector<int> &lcp, vector<pair<int, int> > &trait) {
	// returns = (answer, store-pos, ct1, ct2)
	int baselen = trait[l].second;
	for(int i = l; i < r - 1; ++i) {
		baselen = min(baselen, lcp[i]);
	}
	if(r - l == 1) {
		if(trait[l].first == 1) s1[l].insert(trait[l].second);
		if(trait[l].first == 2) s2[l].insert(trait[l].second);
		return make_tuple(1LL, l, 0, 0);
	}
	long long ans = 0;
	vector<tuple<int, int, int> > g;
	int pre = l;
	for(int i = l; i < r; ++i) {
		if(i == r - 1 || lcp[i] == baselen) {
			tuple<long long, int, int, int> res = solve(pre, i + 1, lcp, trait);
			ans = max(ans, get<0>(res));
			pre = i + 1;
			g.push_back(make_tuple(get<1>(res), get<2>(res), get<3>(res)));
		}
	}
	int mxpos = -1, mxsize = 0;
	for(int i = 0; i < g.size(); ++i) {
		int sz = s1[get<0>(g[i])].size() + s2[get<0>(g[i])].size();
		if(mxsize < sz) {
			mxsize = sz;
			mxpos = i;
		}
	}
	int p = get<0>(g[mxpos]);
	int ct1 = get<1>(g[mxpos]) * 2, ct2 = get<2>(g[mxpos]) * 2;
	for(int i = 0; i < g.size(); ++i) {
		if(i == mxpos) continue;
		for(int j : s1[get<0>(g[i])]) {
			if(s2[p].find(N - j) != s2[p].end()) ++ct1;
			if(s2[p].find(N - j + 1) != s2[p].end()) ++ct2;
		}
		for(int j : s2[get<0>(g[i])]) {
			if(s1[p].find(N - j) != s1[p].end()) ++ct1;
			if(s1[p].find(N - j + 1) != s1[p].end()) ++ct2;
		}
	}
	for(int i = 0; i < g.size(); ++i) {
		if(i == mxpos) continue;
		for(int j : s1[get<0>(g[i])]) {
			s1[p].insert(j);
		}
		for(int j : s2[get<0>(g[i])]) {
			s2[p].insert(j);
		}
	}
	for(int i = 0; i < g.size(); ++i) {
		if(i == mxpos) continue;
		for(int j : s1[get<0>(g[i])]) {
			if(s2[p].find(N - j) != s2[p].end()) ++ct1;
			if(s2[p].find(N - j + 1) != s2[p].end()) ++ct2;
		}
		for(int j : s2[get<0>(g[i])]) {
			if(s1[p].find(N - j) != s1[p].end()) ++ct1;
			if(s1[p].find(N - j + 1) != s1[p].end()) ++ct2;
		}
	}
	ct1 /= 2; ct2 /= 2;
	ans = max(ans, 1LL * (baselen * 2) * ct1);
	ans = max(ans, 1LL * (baselen * 2 - 1) * ct2);
	return make_tuple(ans, p, ct1, ct2);
}
int main() {
	// step #1. read input
	string S;
	cin >> S;
	N = S.size();
	// step #2. construct suffix array of T = S + "#" + rev(S)
	string RS = S;
	reverse(RS.begin(), RS.end());
	string T = S + "#" + RS;
	vector<int> sa_inv(2 * N + 1);
	for(int i = 0; i < 2 * N + 1; ++i) {
		sa_inv[i] = int(T[i]);
	}
	for(int i = 1; i < 2 * N + 1; i *= 2) {
		vector<pair<int, int> > nseq(2 * N + 1);
		for(int j = 0; j < 2 * N + 1; ++j) {
			nseq[j] = make_pair(sa_inv[j], j + i < 2 * N + 1 ? sa_inv[j + i] : -1);
		}
		vector<pair<int, int> > sseq(nseq);
		sort(sseq.begin(), sseq.end());
		sseq.erase(unique(sseq.begin(), sseq.end()), sseq.end());
		for(int j = 0; j < 2 * N + 1; ++j) {
			sa_inv[j] = lower_bound(sseq.begin(), sseq.end(), nseq[j]) - sseq.begin();
		}
	}
	vector<int> sa(2 * N + 1);
	for(int i = 0; i < 2 * N + 1; ++i) {
		sa[sa_inv[i]] = i;
	}
	// step #3. construct rolling-hash table and rolling-hash function
	const int mod = 469762049;
	const int base = 311;
	vector<int> pw(2 * N + 2), h(2 * N + 2);
	pw[0] = 1;
	for(int i = 0; i < 2 * N + 1; ++i) {
		pw[i + 1] = 1LL * pw[i] * base % mod;
		h[i + 1] = (1LL * h[i] * base + T[i]) % mod;
	}
	function<int(int, int)> gethash = [&](int l, int r) {
		return (h[r] - 1LL * h[l] * pw[r - l] % mod + mod) % mod;
	};
	// step #4. calculate LCP
	vector<int> lcp(2 * N);
	for(int i = 0; i < 2 * N; ++i) {
		int l = 0, r = (2 * N + 1) - max(sa[i], sa[i + 1]) + 1;
		while(r - l > 1) {
			int m = (l + r) >> 1;
			if(gethash(sa[i], sa[i] + m) == gethash(sa[i + 1], sa[i + 1] + m)) l = m;
			else r = m;
		}
		lcp[i] = l;
	}
	// step #5. calculate types and lengths of elements in suffix array
	vector<pair<int, int> > trait(2 * N + 1);
	for(int i = 0; i < 2 * N + 1; ++i) {
		if(sa[i] == N) trait[i] = make_pair(0, -1);
		else if(sa[i] < N) trait[i] = make_pair(1, N - sa[i]);
		else trait[i] = make_pair(2, (2 * N + 1) - sa[i]);
	}
	// step #6. calculate the answer
	tuple<long long, int, int, int> ans = solve(1, 2 * N + 1, lcp, trait);
	// step #7. print the answer
	cout << get<0>(ans) << endl;
	return 0;
}

Compilation message

palindrome.cpp: In function 'std::tuple<long long int, int, int, int> solve(int, int, std::vector<int>&, std::vector<std::pair<int, int> >&)':
palindrome.cpp:35:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for(int i = 0; i < g.size(); ++i) {
      |                 ~~^~~~~~~~~~
palindrome.cpp:44:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int i = 0; i < g.size(); ++i) {
      |                 ~~^~~~~~~~~~
palindrome.cpp:55:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(int i = 0; i < g.size(); ++i) {
      |                 ~~^~~~~~~~~~
palindrome.cpp:64:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for(int i = 0; i < g.size(); ++i) {
      |                 ~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 66040 KB Output is correct
2 Correct 46 ms 66040 KB Output is correct
3 Correct 47 ms 66040 KB Output is correct
4 Correct 49 ms 66304 KB Output is correct
5 Correct 45 ms 66040 KB Output is correct
6 Correct 46 ms 66040 KB Output is correct
7 Correct 46 ms 66040 KB Output is correct
8 Correct 47 ms 66168 KB Output is correct
9 Correct 47 ms 66044 KB Output is correct
10 Correct 48 ms 66040 KB Output is correct
11 Correct 46 ms 66040 KB Output is correct
12 Correct 46 ms 66048 KB Output is correct
13 Correct 47 ms 66040 KB Output is correct
14 Correct 46 ms 66040 KB Output is correct
15 Correct 46 ms 66040 KB Output is correct
16 Correct 45 ms 66048 KB Output is correct
17 Correct 46 ms 66040 KB Output is correct
18 Correct 46 ms 66176 KB Output is correct
19 Correct 46 ms 66168 KB Output is correct
20 Correct 49 ms 66040 KB Output is correct
21 Correct 46 ms 66040 KB Output is correct
22 Correct 47 ms 66040 KB Output is correct
23 Correct 46 ms 66168 KB Output is correct
24 Correct 47 ms 66040 KB Output is correct
25 Correct 46 ms 66040 KB Output is correct
26 Correct 49 ms 66040 KB Output is correct
27 Correct 46 ms 66040 KB Output is correct
28 Correct 46 ms 66040 KB Output is correct
29 Correct 46 ms 66040 KB Output is correct
30 Correct 46 ms 66040 KB Output is correct
31 Correct 46 ms 66040 KB Output is correct
32 Correct 47 ms 66040 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 66552 KB Output is correct
2 Correct 54 ms 66552 KB Output is correct
3 Correct 51 ms 66552 KB Output is correct
4 Correct 50 ms 66432 KB Output is correct
5 Correct 59 ms 66552 KB Output is correct
6 Correct 52 ms 66552 KB Output is correct
7 Correct 56 ms 66680 KB Output is correct
8 Correct 51 ms 66552 KB Output is correct
9 Correct 55 ms 66428 KB Output is correct
10 Correct 53 ms 66416 KB Output is correct
11 Correct 57 ms 66424 KB Output is correct
12 Correct 51 ms 66684 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 71580 KB Output is correct
2 Correct 156 ms 70232 KB Output is correct
3 Correct 309 ms 71196 KB Output is correct
4 Correct 255 ms 70940 KB Output is correct
5 Correct 115 ms 71196 KB Output is correct
6 Correct 117 ms 71324 KB Output is correct
7 Correct 128 ms 70424 KB Output is correct
8 Correct 134 ms 70684 KB Output is correct
9 Correct 134 ms 70684 KB Output is correct
10 Correct 129 ms 73880 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 73120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1084 ms 79200 KB Time limit exceeded
2 Halted 0 ms 0 KB -