oj.uz

답안 #104494

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
104494 2019-04-07T08:06:23 Z E869120 회문 (APIO14_palindrome) C++14
23 / 100
 1000 ms 31140 KB 
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

class RollingHash {
public:
	long long BASE = 311LL, INV = 9134400602415662215LL;
	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);
		inv.push_back(1); for (int i = 0; i < str.size(); i++) inv.push_back(inv[i] * INV);
		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));
		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));
		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]) * inv[l];
	}
	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]) * inv[(int)S.size() - (r + 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: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);
                                     ~~^~~~~~~~~~~~
palindrome.cpp:17: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));
                                             ~~^~~~~~~~~~~~
palindrome.cpp:18: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));
                                             ~~^~~~~~~~~~~~
palindrome.cpp: In member function 'long long int RollingHash::get_val1(long long int, long long int)':
palindrome.cpp:22: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:28: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:32: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:71:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < A1.size(); i++) {
                  ~~^~~~~~~~~~~
palindrome.cpp:74:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i == A1.size() - 1) break;
       ~~^~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 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 2 ms 384 KB Output is correct
5 Correct 2 ms 356 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 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 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 2 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 2 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 0 ms 384 KB Output is correct
25 Correct 3 ms 384 KB Output is correct
26 Correct 2 ms 384 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 2 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 3 ms 384 KB Output is correct
32 Correct 2 ms 384 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 7 ms 504 KB Output is correct
5 Correct 7 ms 640 KB Output is correct
6 Correct 8 ms 384 KB Output is correct
7 Correct 8 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 7 ms 512 KB Output is correct
10 Correct 7 ms 512 KB Output is correct
11 Correct 7 ms 512 KB Output is correct
12 Correct 8 ms 560 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 227 ms 1428 KB Output is correct
2 Correct 269 ms 1428 KB Output is correct
3 Correct 300 ms 1612 KB Output is correct
4 Correct 274 ms 1544 KB Output is correct
5 Correct 284 ms 1432 KB Output is correct
6 Correct 313 ms 1548 KB Output is correct
7 Correct 282 ms 1588 KB Output is correct
8 Correct 266 ms 1484 KB Output is correct
9 Correct 293 ms 1592 KB Output is correct
10 Incorrect 290 ms 1616 KB Output isn't correct

Subtask #4
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1059 ms 10352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1044 ms 31140 KB Time limit exceeded
2 Halted 0 ms 0 KB -