oj.uz

Submission #552141

# Submission time Handle Problem Language Result Execution time Memory
552141 2022-04-22T13:31:54 Z QwertyPi Palindromes (APIO14_palindrome) C++14
100 / 100
 889 ms 52948 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 312 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 312 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 304 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 308 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 448 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 440 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1744 KB Output is correct
2 Correct 14 ms 1744 KB Output is correct
3 Correct 20 ms 1776 KB Output is correct
4 Correct 21 ms 1832 KB Output is correct
5 Correct 16 ms 1760 KB Output is correct
6 Correct 19 ms 1804 KB Output is correct
7 Correct 19 ms 1724 KB Output is correct
8 Correct 16 ms 2104 KB Output is correct
9 Correct 18 ms 2100 KB Output is correct
10 Correct 21 ms 1844 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 12492 KB Output is correct
2 Correct 164 ms 12648 KB Output is correct
3 Correct 234 ms 12740 KB Output is correct
4 Correct 248 ms 12604 KB Output is correct
5 Correct 198 ms 14156 KB Output is correct
6 Correct 197 ms 13872 KB Output is correct
7 Correct 245 ms 12692 KB Output is correct
8 Correct 205 ms 16816 KB Output is correct
9 Correct 205 ms 16280 KB Output is correct
10 Correct 257 ms 16080 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 40804 KB Output is correct
2 Correct 591 ms 40732 KB Output is correct
3 Correct 762 ms 40728 KB Output is correct
4 Correct 889 ms 40700 KB Output is correct
5 Correct 666 ms 43448 KB Output is correct
6 Correct 679 ms 40960 KB Output is correct
7 Correct 787 ms 40968 KB Output is correct
8 Correct 666 ms 52948 KB Output is correct
9 Correct 672 ms 52904 KB Output is correct
10 Correct 825 ms 44616 KB Output is correct
11 Correct 608 ms 44680 KB Output is correct
12 Correct 664 ms 52332 KB Output is correct