oj.uz

Submission #592927

# Submission time Handle Problem Language Result Execution time Memory
592927 2022-07-09T20:15:03 Z 1ne Palindromes (APIO14_palindrome) C++14
23 / 100
 1000 ms 15964 KB 
#include<bits/stdc++.h>
using namespace std;
struct String_Hash{
	int p1 = 31;
	int p2 = 37;
	int n;
	const int mod1 = 1e9 + 7;
	const int mod2 = 1e9 + 9;
	vector<int>h1,h2;
	vector<int>pw1,pw2;
	void build(int N){
		n = N;
		h1.resize(n + 1,0);
		pw1.resize(n,0);
		h2.resize(n + 1,0);
		pw2.resize(n,0);
		pw1[0] = 1;
		pw2[0] = 1;
		for (int i = 0;i<n;++i){
			pw1[i] = (pw1[i - 1] * p1)%mod1;
			pw2[i] = (pw2[i - 1] * p2)%mod2;
		}
	}
	void compute_hash(string &s){
		for (int i = 0;i<n;++i){
			h1[i + 1] = (h1[i] + (s[i] - 'a' + 1) * pw1[i])%mod1;
			h2[i + 1] = (h2[i] + (s[i] - 'a' + 1) * pw2[i])%mod2;
		}
	}
	pair<int,int> gethash(int l,int r){
		//h[r] = h[l]*p[l - 1] + h[l + 1]* p[l].... h[r - 1] * p[r - 2]
		//h[l] = ...h[l - 1]*p[l - 2] + h[l]* p[l - 1]
		int cur_h1 = (h1[r] - h1[l] + mod1)%mod1;
		int cur_h2 = (h2[r] - h2[l] + mod2)%mod2;
		cur_h1 = (cur_h1 * pw1[n - l - 1])%mod1;
		cur_h2 = (cur_h2 * pw2[n - l - 1])%mod2;
		return make_pair(cur_h1,cur_h2);
	}
};
struct Manacher{
	string cur;
	vector<int>p;
	int n;
	void build(string s){
		n = (int)s.length();
		cur+='@';
		for (int i = 0;i<n;++i){
			cur+='#';
			cur+=s[i];
		}	
		cur+='#';
		cur+='$';
		n = 2 * n + 3;
		p.resize(n + 1);
		int l = 0,r = 0;
		for (int i = 1;i<n;++i){
			if (i < r){
				p[i] = min(r - i,p[l + (r - i)]);
			}
			while(cur[i - p[i] - 1] == cur[i + p[i] + 1])++p[i];
			if (r < i + p[i]){
				r = i + p[i];
				l = i - p[i];
			}
		}
	}
	string lpalin(){
		int sz = 0,ind = -1;
		for (int i = 0;i<=n;++i){
			int cursz = 0;
			if (cur[i] == '#'){
				cursz  = (p[i] + 1)/2 + (p[i] + 1)/2;
			}
			else{
				cursz = p[i]/2 + p[i]/2 + 1;
			}
			if (sz < cursz){
				sz = cursz;
				ind = i;
			}
		}
		string ans;
		for (int i = ind - p[ind];i<=ind + p[ind];++i){
			if (cur[i]!='#')ans+=cur[i];
		}
		return ans;
	}
};

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	string s;cin>>s;
	Manacher st;
	st.build(s);
	map<string,int>mp;
	String_Hash h;
	h.build((int)s.length());
	h.compute_hash(s);
	for (int i = 1;i<st.n;++i){
		if (st.p[i]){
			int l = (i - 1 - st.p[i])/2;
			int r = l + st.p[i] - 1;
			while(l<=r){
				//cout<<l<<" "<<r<<'\n';
				mp[s.substr(l,r - l + 1)]++;
				++l;
				--r;
			}
		}
	}
	int ans = 0;
	for (auto x:mp){
		ans = max(ans,(int)x.first.length() * x.second);
	}
	cout<<ans<<'\n';
	return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 892 KB Output is correct
2 Correct 17 ms 596 KB Output is correct
3 Correct 99 ms 944 KB Output is correct
4 Correct 4 ms 380 KB Output is correct
5 Correct 100 ms 852 KB Output is correct
6 Correct 94 ms 844 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 47 ms 900 KB Output is correct
9 Correct 2 ms 480 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 704 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 7864 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 10420 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 15964 KB Time limit exceeded
2 Halted 0 ms 0 KB -