Submission #552141

#	Time	Username	Problem	Language	Result	Execution time	Memory
552141		QwertyPi	Palindromes (APIO14_palindrome)	C++14	100 / 100	889 ms	52948 KiB

palindrome

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back

using namespace std;
typedef pair<int, int> pii;
const int N = 3e5+1;

const int MOD1 = 1000000007,
		  MOD2 =  999999937;
const int 	a1 =  235829684,
			a2 =  398593609;
int pm(int a, int b, int mod){
	if(b == 0) return 1;
	return pm(a * a % mod, b / 2, mod) * (b % 2 ? a : 1) % mod;
}

int mi(int a, int mod){
	return pm(a, mod - 2, mod);
}

struct StrHash{
	int ha[N], pw[N], a, p;
	void prec(string& s, int a, int p){
		StrHash::a = a; StrHash::p = p;
		pw[0] = 1; for(int i = 0; i < s.size(); i++) pw[i + 1] = pw[i] * a % p;
		for(int i = 0; i < s.size(); i++){
			ha[i + 1] = (ha[i] * a + s[i]) % p;
		}
	}
	int hash(int l, int r){
		int ret = ha[r + 1] - ha[l] * pw[r - l + 1]; 
		return (ret % p + p) % p;
	}
} hpf[2], hsf[2];

int n;
bool isPal(int l, int r){
	bool ok = true;
	for(int i = 0; i < 2; i++){
		ok &= hpf[i].hash(l, r) == hsf[i].hash(n - 1 - r, n - 1 - l);
	}
	return ok;
}

int mx_pal[N * 2 + 1]; 

pii hashing(int l, int r){
	return {hpf[0].hash(l, r), hpf[1].hash(l, r)};
}

pii hashing(tuple<int, int, int> t){
	return {hpf[0].hash(get<0>(t), get<1>(t)), hpf[1].hash(get<0>(t), get<1>(t))};
}
int32_t main(){
	string s;
	cin >> s;
	n = s.size();
	hpf[0].prec(s, a1, MOD1); hpf[1].prec(s, a2, MOD2);
	reverse(s.begin(), s.end());
	hsf[0].prec(s, a1, MOD1); hsf[1].prec(s, a2, MOD2);
	reverse(s.begin(), s.end());
	for(int i = 0; i <= (n - 1) * 2; i++){
		int l = i / 2, r = (i + 1) / 2;
		if(s[l] != s[r]) continue;
		int ql = 0, qr = min(l - 0, n - 1 - r);
		while(ql != qr){
			int qm = (ql + qr + 1) / 2;
			if(isPal(l - qm, r + qm)){
				ql = qm;
			}else{
				qr = qm - 1;
			}
		}
		mx_pal[i] = ql + 1;
	}
	// for(int i = 0; i <= (n - 1) * 2; i++) cout << mx_pal[i] << (i == (n - 1) * 2 ? '\n' : ' ');
	int ans = 0;
	vector<pii> mx_len;
	for(int i = 0; i <= (n - 1) * 2; i++){
		mx_len.pb({mx_pal[i] * 2 - (i % 2 == 0), i});
	}
	sort(mx_len.begin(), mx_len.end(), greater<>());
//	for(auto i : mx_len){
//		cout << i.fi << ' ' << i.se << '\n';
//	}
	int idx = 0;
	vector<tuple<int, int, int>> hashs;
	for(int len = n; len >= 1; len -= 2){
		while(idx < mx_len.size() && mx_len[idx].fi >= len){
			if(mx_len[idx].fi == len) hashs.pb({mx_len[idx].se / 2 - (mx_len[idx].fi - 1) / 2, (mx_len[idx].se + 1) / 2 + (mx_len[idx].fi - 1) / 2, 1});
			idx++;
		}
		sort(hashs.begin(), hashs.end(), [](tuple<int, int, int> a, tuple<int, int, int> b){
			return hashing(a) < hashing(b);
		});
		vector<tuple<int, int, int>> new_hashs;
		for(int i = 1; i < hashs.size(); i++){
			if(hashing(hashs[i]) == hashing(hashs[i - 1])){
				get<2>(hashs[i]) += get<2>(hashs[i - 1]);
				get<2>(hashs[i - 1]) = 0;
			}
		}
		for(auto i : hashs){
			ans = max(ans, get<2>(i) * len);
			if(get<2>(i) != 0) new_hashs.pb({get<0>(i) + 1, get<1>(i) - 1, get<2>(i)});
		}
		swap(hashs, new_hashs);
	}
	idx = 0;
	hashs.clear();
	for(int len = n - 1; len >= 1; len -= 2){
		while(idx < mx_len.size() && mx_len[idx].fi >= len){
			if(mx_len[idx].fi == len) hashs.pb({mx_len[idx].se / 2 - (mx_len[idx].fi - 1) / 2, (mx_len[idx].se + 1) / 2 + (mx_len[idx].fi - 1) / 2, 1});
			idx++;
		}
		sort(hashs.begin(), hashs.end(), [](tuple<int, int, int> a, tuple<int, int, int> b){
			return hashing(a) < hashing(b);
		});
		vector<tuple<int, int, int>> new_hashs;
		for(int i = 1; i < hashs.size(); i++){
			if(hashing(hashs[i]) == hashing(hashs[i - 1])){
				get<2>(hashs[i]) += get<2>(hashs[i - 1]);
				get<2>(hashs[i - 1]) = 0;
			}
		}
		for(auto i : hashs){
			ans = max(ans, get<2>(i) * len);
			if(get<2>(i) != 0) new_hashs.pb({get<0>(i) + 1, get<1>(i) - 1, get<2>(i)});
		}
		swap(hashs, new_hashs);
	}
	cout << ans << endl;
}

Compilation message (stderr)

palindrome.cpp: In member function 'void StrHash::prec(std::string&, long long int, long long int)':
palindrome.cpp:28:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   pw[0] = 1; for(int i = 0; i < s.size(); i++) pw[i + 1] = pw[i] * a % p;
      |                             ~~^~~~~~~~~~
palindrome.cpp:29:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for(int i = 0; i < s.size(); i++){
      |                  ~~^~~~~~~~~~
palindrome.cpp: In function 'int32_t main()':
palindrome.cpp:92:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   while(idx < mx_len.size() && mx_len[idx].fi >= len){
      |         ~~~~^~~~~~~~~~~~~~~
palindrome.cpp:100:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |   for(int i = 1; i < hashs.size(); i++){
      |                  ~~^~~~~~~~~~~~~~
palindrome.cpp:115:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |   while(idx < mx_len.size() && mx_len[idx].fi >= len){
      |         ~~~~^~~~~~~~~~~~~~~
palindrome.cpp:123:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |   for(int i = 1; i < hashs.size(); i++){
      |                  ~~^~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27