Submission #104492

#	Time	Username	Problem	Language	Result	Execution time	Memory
104492		E869120	회문 (APIO14_palindrome)	C++14	23 / 100	1066 ms	28776 KiB

palindrome

#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 (stderr)

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 / 8
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27