Submission #552104

#	Time	Username	Problem	Language	Result	Execution time	Memory
552104		QwertyPi	Palindromes (APIO14_palindrome)	C++14	23 / 100	526 ms	131072 KiB

palindrome

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

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]; 
int32_t main(){
	string s;
	cin >> s;
	n = s.size();
	vector<tuple<int, int, int>> hashs;
	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);
	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] << ' ';
//	}
//	cout << endl;
	for(int i = 0; i <= (n - 1) * 2; i++){
		int l = i / 2, r = (i + 1) / 2;
		for(int d = 0; d < mx_pal[i]; d++){
			hashs.push_back({hpf[0].hash(l - d, r + d), hpf[1].hash(l - d, r + d), (r - l + 1) + d * 2});
		}
	}
	sort(hashs.begin(), hashs.end());
	int h1 = 0, h2 = 0, cnt = 0, len = 0, ans = 0;
	for(auto i : hashs){
		if(get<0>(i) != h1 || get<1>(i) != h2){
			h1 = get<0>(i), h2 = get<1>(i);
			cnt = 1, len = get<2>(i), ans = max(ans, cnt * len);
		}else{
			cnt++;
			ans = max(ans, cnt * len);
		}
	}
	cout << ans << endl;
}

Compilation message (stderr)

palindrome.cpp: In member function 'void StrHash::prec(std::string&, long long int, long long int)':
palindrome.cpp:27: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]
   27 |   pw[0] = 1; for(int i = 0; i < s.size(); i++) pw[i + 1] = pw[i] * a % p;
      |                             ~~^~~~~~~~~~
palindrome.cpp:28: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]
   28 |   for(int i = 0; i < s.size(); i++){
      |                  ~~^~~~~~~~~~

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