oj.uz

Submission #104498

# Submission time Handle Problem Language Result Execution time Memory
104498 2019-04-07T08:22:46 Z E869120 Palindromes (APIO14_palindrome) C++14
47 / 100
 1000 ms 31112 KB 
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
#pragma warning (disable: 4996)

class RollingHash {
public:
	long long BASE = 1000000009LL, INV = 1943136735LL, MOD = 2147483647LL;
	string S; vector<long long>hash_value1, hash_value2, power, inv;

	void init(string str) {
		S = str;
		power.push_back(1); for (int i = 0; i < str.size(); i++) power.push_back((power[i] * BASE) % MOD);
		inv.push_back(1); for (int i = 0; i < str.size(); i++) inv.push_back((inv[i] * INV) % MOD);
		hash_value1.push_back(0); for (int i = 0; i < str.size(); i++) hash_value1.push_back((hash_value1[i] + 1LL * power[i] * (str[i] - 'a' + 1)) % MOD);
		hash_value2.push_back(0); for (int i = 0; i < str.size(); i++) hash_value2.push_back((hash_value2[i] + 1LL * power[i] * (str[str.size() - 1 - i] - 'a' + 1)) % MOD);
		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] + MOD) * inv[l] % MOD;
	}
	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] + MOD) * inv[(int)S.size() - (r + 1)] % MOD;
	}
	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:7:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
palindrome.cpp: In member function 'void RollingHash::init(std::__cxx11::string)':
palindrome.cpp:16: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) % MOD);
                                       ~~^~~~~~~~~~~~
palindrome.cpp:17:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   inv.push_back(1); for (int i = 0; i < str.size(); i++) inv.push_back((inv[i] * INV) % MOD);
                                     ~~^~~~~~~~~~~~
palindrome.cpp:18: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] + 1LL * power[i] * (str[i] - 'a' + 1)) % MOD);
                                             ~~^~~~~~~~~~~~
palindrome.cpp:19: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] + 1LL * power[i] * (str[str.size() - 1 - i] - 'a' + 1)) % MOD);
                                             ~~^~~~~~~~~~~~
palindrome.cpp: In member function 'long long int RollingHash::get_val1(long long int, long long int)':
palindrome.cpp:23: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:29: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:33: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:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < A1.size(); i++) {
                  ~~^~~~~~~~~~~
palindrome.cpp:77: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 3 ms 384 KB Output is correct
4 Correct 2 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 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 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 2 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 3 ms 384 KB Output is correct
23 Correct 3 ms 384 KB Output is correct
24 Correct 3 ms 384 KB Output is correct
25 Correct 2 ms 384 KB Output is correct
26 Correct 3 ms 384 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 3 ms 384 KB Output is correct
29 Correct 3 ms 384 KB Output is correct
30 Correct 4 ms 384 KB Output is correct
31 Correct 3 ms 384 KB Output is correct
32 Correct 3 ms 428 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 1496 KB Output is correct
2 Correct 260 ms 1532 KB Output is correct
3 Correct 297 ms 1468 KB Output is correct
4 Correct 274 ms 1548 KB Output is correct
5 Correct 309 ms 1548 KB Output is correct
6 Correct 312 ms 1548 KB Output is correct
7 Correct 293 ms 1548 KB Output is correct
8 Correct 321 ms 1492 KB Output is correct
9 Correct 311 ms 1448 KB Output is correct
10 Correct 286 ms 1444 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1018 ms 10340 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 1079 ms 31112 KB Time limit exceeded
2 Halted 0 ms 0 KB -