oj.uz

Submission #104492

# Submission time Handle Problem Language Result Execution time Memory
104492 2019-04-07T07:59:31 Z E869120 Palindromes (APIO14_palindrome) C++14
23 / 100
 1000 ms 28776 KB 
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

class RollingHash {
public:
	long long BASE = 311LL;
	string S; vector<long long>hash_value1, hash_value2, power;

	void init(string str) {
		S = str;
		power.push_back(1); for (int i = 0; i < str.size(); i++) power.push_back(power[i] * BASE);
		hash_value1.push_back(0); for (int i = 0; i < str.size(); i++) hash_value1.push_back(hash_value1[i] * BASE + (str[i] - 'a' + 1));
		hash_value2.push_back(0); for (int i = 0; i < str.size(); i++) hash_value2.push_back(hash_value2[i] * BASE + (str[str.size() - 1 - i] - 'a' + 1));
		reverse(hash_value2.begin(), hash_value2.end());
	}
	long long get_val1(long long l, long long r) {
		if (r >= S.size()) return 100000000000000000LL + l;
		// 区間 [l, r] について
		return (hash_value1[r + 1] - hash_value1[l] * power[r - l + 1]);
	}
	long long get_val2(long long l, long long r) {
		// 区間 [l, r] について
		if (r >= S.size()) return 100000000000000000LL + l;
		return (hash_value2[l] - hash_value2[r + 1] * power[r - l + 1]);
	}
	bool ispalindrome(long long l, long long r) {
		if (l < 0 || r >= S.size()) return false;
		long long v1 = get_val1(l, r);
		long long v2 = get_val2(l, r);
		if (v1 == v2) return true;
		return false;
	}
};

long long N, A[1 << 19], C[1 << 19], D[1 << 19]; string S;
RollingHash Z;

void SuffixArray() {
	for (int i = 0; i < N; i++) A[i] = (S[i] - 'a' + 1);
	for (int i = 0; i < 19; i++) {
		for (int j = 0; j < N; j++) {
			long long v1 = A[j], v2 = 0; if (j + (1 << i) < N) v2 = A[j + (1 << i)];
			A[j] = v1 * 1000000LL + v2;
		}
		vector<pair<long long, int>>vec;
		for (int j = 0; j < N; j++) vec.push_back(make_pair(A[j], j));
		sort(vec.begin(), vec.end());

		int pos = 0;
		for (int j = 0; j < N; j++) {
			A[vec[j].second] = pos + 1;
			if (j < N - 1 && vec[j].first != vec[j + 1].first) pos = j + 1;
		}
	}

	vector<pair<long long, int>> E;
	for (int j = 0; j < N; j++) E.push_back(make_pair(A[j], j));
	sort(E.begin(), E.end());
	for (int j = 0; j < N; j++) A[j] = E[j].second;
}

long long calc(vector<long long>A1, vector<long long>A2, long long BASE) {
	vector<long long>V(N + 1, 0);

	long long maxn = 0;
	for (int i = 0; i < A1.size(); i++) {
		for (int j = 0; j <= A1[i]; j++) V[j] += 2LL * j + BASE;
		for (int j = 0; j <= N; j++) maxn = max(maxn, V[j]);
		if (i == A1.size() - 1) break;
		for (int j = A2[i] + 1; j <= N; j++) V[j] = 0;
	}
	return maxn;
}

long long solve_val1() {
	for (int i = 0; i < N; i++) {
		int L = 0, R = N, M; C[i] = 0;
		for (int j = 0; j < 25; j++) {
			M = (L + R) / 2;
			int cl = A[i] - M, cr = A[i] + M;
			if (Z.ispalindrome(cl, cr) == true) { C[i] = max(C[i], 1LL * M + 1LL); L = M; }
			else { R = M; }
		}
	}

	for (int i = 0; i < N - 1; i++) {
		int L = 0, R = N, M; D[i] = 0;
		int d1 = A[i], d2 = A[i + 1];

		for (int j = 0; j < 25; j++) {
			M = (L + R) / 2;
			if (Z.get_val1(d1, d1 + M - 1) == Z.get_val1(d2, d2 + M - 1)) { D[i] = max(D[i], 1LL * M); L = M; }
			else { R = M; }
		}
	}

	vector<long long> B1, B2;
	for (int i = 0; i < N; i++) B1.push_back(C[i]);
	for (int i = 0; i < N - 1; i++) B2.push_back(D[i]);
	return calc(B1, B2, -1);
}

long long solve_val2() {
	for (int i = 0; i < N; i++) {
		int L = 0, R = N, M; C[i] = 0;
		for (int j = 0; j < 25; j++) {
			M = (L + R) / 2;
			int cl = A[i] - M - 1, cr = A[i] + M;
			if (Z.ispalindrome(cl, cr) == true) { C[i] = max(C[i], 1LL * M + 1LL); L = M; }
			else { R = M; }
		}
	}

	for (int i = 0; i < N - 1; i++) {
		int L = 0, R = N, M; D[i] = 0;
		int d1 = A[i], d2 = A[i + 1];

		for (int j = 0; j < 25; j++) {
			M = (L + R) / 2;
			if (Z.get_val1(d1, d1 + M - 1) == Z.get_val1(d2, d2 + M - 1)) { D[i] = max(D[i], 1LL * M); L = M; }
			else { R = M; }
		}
	}

	vector<long long> B1, B2;
	for (int i = 0; i < N; i++) B1.push_back(C[i]);
	for (int i = 0; i < N - 1; i++) B2.push_back(D[i]);
	return calc(B1, B2, 0);
}

int main() {
	cin >> S; N = S.size();
	Z.init(S);
	SuffixArray();

	long long v1 = solve_val1();
	long long v2 = solve_val2();
	cout << max(v1, v2) << endl;
	return 0;
}

Compilation message

palindrome.cpp: In member function 'void RollingHash::init(std::__cxx11::string)':
palindrome.cpp:15:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   power.push_back(1); for (int i = 0; i < str.size(); i++) power.push_back(power[i] * BASE);
                                       ~~^~~~~~~~~~~~
palindrome.cpp:16:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   hash_value1.push_back(0); for (int i = 0; i < str.size(); i++) hash_value1.push_back(hash_value1[i] * BASE + (str[i] - 'a' + 1));
                                             ~~^~~~~~~~~~~~
palindrome.cpp:17:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   hash_value2.push_back(0); for (int i = 0; i < str.size(); i++) hash_value2.push_back(hash_value2[i] * BASE + (str[str.size() - 1 - i] - 'a' + 1));
                                             ~~^~~~~~~~~~~~
palindrome.cpp: In member function 'long long int RollingHash::get_val1(long long int, long long int)':
palindrome.cpp:21:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (r >= S.size()) return 100000000000000000LL + l;
       ~~^~~~~~~~~~~
palindrome.cpp: In member function 'long long int RollingHash::get_val2(long long int, long long int)':
palindrome.cpp:27:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (r >= S.size()) return 100000000000000000LL + l;
       ~~^~~~~~~~~~~
palindrome.cpp: In member function 'bool RollingHash::ispalindrome(long long int, long long int)':
palindrome.cpp:31:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (l < 0 || r >= S.size()) return false;
                ~~^~~~~~~~~~~
palindrome.cpp: In function 'long long int calc(std::vector<long long int>, std::vector<long long int>, long long int)':
palindrome.cpp:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < A1.size(); i++) {
                  ~~^~~~~~~~~~~
palindrome.cpp:73:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i == A1.size() - 1) break;
       ~~^~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 3 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 3 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 2 ms 384 KB Output is correct
26 Correct 2 ms 384 KB Output is correct
27 Correct 3 ms 384 KB Output is correct
28 Correct 0 ms 384 KB Output is correct
29 Correct 3 ms 384 KB Output is correct
30 Correct 2 ms 384 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 2 ms 384 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 7 ms 484 KB Output is correct
3 Correct 7 ms 512 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 7 ms 384 KB Output is correct
11 Correct 8 ms 512 KB Output is correct
12 Correct 7 ms 512 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 1420 KB Output is correct
2 Correct 249 ms 1292 KB Output is correct
3 Correct 271 ms 1356 KB Output is correct
4 Correct 281 ms 1360 KB Output is correct
5 Correct 250 ms 1360 KB Output is correct
6 Correct 278 ms 1292 KB Output is correct
7 Correct 291 ms 1300 KB Output is correct
8 Correct 302 ms 1572 KB Output is correct
9 Correct 294 ms 1292 KB Output is correct
10 Incorrect 258 ms 1432 KB Output isn't correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 9488 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 1062 ms 28776 KB Time limit exceeded
2 Halted 0 ms 0 KB -