oj.uz

Submission #1113948

# Submission time Handle Problem Language Result Execution time Memory
1113948 2024-11-17T21:57:35 Z KarolZ Palindromes (APIO14_palindrome) C++17
100 / 100
 973 ms 76484 KB 
#include<bits/stdc++.h>
#include<unordered_map>
#pragma GCC optimize "Ofast"
using namespace std;
typedef __int128 ll;
const ll x=31;
const ll mod=1000000000000000009;
ll hasz[300010][2];
ll pot[300010];
ll odw[300010];
string s;
ll spr(bool b,int kt){
	if(kt<0||kt>=s.size())return 0;
	return hasz[kt][b];
}
void haszuj(){
	for(int i=0;i<s.size();i++){
		hasz[i][0]=(spr(0,i-1)*x+s[i]-'a'+1)%mod;
		hasz[i][1]=((s[i]-'a'+1)*pot[i]+spr(1,i-1))%mod;
	}
	return;
}
ll ferm(ll xx){
	ll wyn=1,pott=mod-2;
	while(pott){
		if(pott%2)wyn*=xx;
		xx*=xx;
		xx%=mod;
		wyn%=mod;
		pott/=2;
	}
	return wyn;
}
int bs(int a,bool b){
	ll vp=1,vs,vk=s.size(),od=0;
	while(vp<=vk){
		vs=(vp+vk)/2;
		if(a+vs-1>=s.size()||a-vs+(b^1)<0)vk=vs-1;
		else{
			/*if(a==154){
				if(vs==1)cout<<(long long)((hasz[a+vs-1][0]-(spr(0,a-vs+(b^1)-1)*pot[vs+vs-(b^1)-1+1])%mod+mod)%mod)<<' '<<(long long)((((hasz[a+vs-1][1]-spr(1,a-vs+(b^1)-1))*odw[a-vs+(b^1)]))%mod)<<'\n';
			}*/
			if((hasz[a+vs-1][0]-(spr(0,a-vs+(b^1)-1)*pot[vs+vs-(b^1)-1+1])%mod+mod)%mod==(((hasz[a+vs-1][1]-spr(1,a-vs+(b^1)-1)+mod)*odw[a-vs+(b^1)]))%mod){
				vp=vs+1;
				od=vs;
			}
			else vk=vs-1;
		}
	}
	return od;
}
unordered_map<long long,pair<pair<ll,ll>,ll> >m[2];//klucz - hasz polowy palindromu, parzystosc //// wartosci - glebokosc, ile(suma prefixowa), skad
void upd(int a,int il,bool b){
	int pom=il;
	if(il==0)return;
	while(m[b].find((hasz[a+il-1][0]-(spr(0,a-1)*pot[il])%mod+mod)%mod)==m[b].end()){
		if(il<=1){
			m[b][((hasz[a+il-1][0]-(spr(0,a-1)*pot[il])%mod)+mod)%mod]={{1,0},0};
			//cout<<"x ";
			break;
		}
		il--;
	}
	//cout<<(long long)((hasz[a+il-1][0]-spr(0,a-1)*pot[il])%mod)<<' ';
	for(int i=il+1;i<=pom;i++){
		m[b][(hasz[a+i-1][0]-(spr(0,a-1)*pot[i])%mod+mod)%mod]={{m[b][(hasz[a+i-1-1][0]-(spr(0,a-1)*pot[i-1])%mod+mod)%mod].first.first+1,0},(hasz[a+i-1-1][0]-(spr(0,a-1)*pot[i-1])%mod+mod)%mod};
	//	cout<<(long long)((hasz[a+i-1][0]-spr(0,a-1)*pot[i])%mod)<<' ';
	}
	//cout<<'\n';
	m[b][(hasz[a+pom-1][0]-(spr(0,a-1)*pot[pom])%mod+mod)%mod].first.second++;
	//cout<<(long long)((hasz[a+pom-1][0]-spr(0,a-1)*pot[pom])%mod)<<' '<<(long long)m[b][(hasz[a+pom-1][0]-spr(0,a-1)*pot[pom])%mod].first.second<<'\n';
	//cout<<b<<' '<<"dodaje\n";
	return;
}
pair<ll,ll>deefes(ll a,bool b){
	ll sum=m[b][a].first.second,wyn=0;
	//cout<<"deefes wchodzi do hasza: "<<(long long)a<<'\n';
	for(int i='a';i<='z';i++){
	//	cout<<"z "<<(long long)a<<" do "<<(long long)((a*x+i-'a'+1)%mod)<<'\n';
		if(m[b].find((a*x+i-'a'+1)%mod)!=m[b].end()){
			pair<ll,ll>p=deefes((a*x+i-'a'+1)%mod,b);
			wyn=max(wyn,p.first);
			sum+=p.second;
		}
	}
	//cout<<(long long)a<<' '<<b<<' '<<(long long)m[b][a].first.first<<' '<<(long long)sum<<'\n';
	return {max((m[b][a].first.first*2-(b^1))*sum,wyn),sum};
}
int main(){
//ios_base::sync_with_stdio(0);
//cin.tie(0);
//cout.tie(0);
	cin>>s;
	//cout<<s.size()<<'\n';
	pot[0]=1;
	for(int i=1;i<=s.size();i++)pot[i]=(pot[i-1]*x)%mod;
	odw[s.size()]=ferm(pot[s.size()]);
	for(int i=s.size()-1;i>=0;i--)odw[i]=(odw[i+1]*x)%mod;
	haszuj();
	for(int i=0;i<s.size();i++){
		for(int j=0;j<2;j++){
			int a=bs(i,j);
			//cout<<i<<' '<<j<<' '<<a<<'\n';
			upd(i,a,j);
		}
	}
	m[0][0]={{0,0},0};
	m[1][0]={{0,0},0};
	cout<<(long long)max(deefes(0,0).first,deefes(0,1).first);
	return 0;
}

Compilation message

palindrome.cpp: In function 'll spr(bool, int)':
palindrome.cpp:13:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  if(kt<0||kt>=s.size())return 0;
      |           ~~^~~~~~~~~~
palindrome.cpp: In function 'void haszuj()':
palindrome.cpp:17:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for(int i=0;i<s.size();i++){
      |              ~^~~~~~~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:96:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |  for(int i=1;i<=s.size();i++)pot[i]=(pot[i-1]*x)%mod;
      |              ~^~~~~~~~~~
palindrome.cpp:100:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for(int i=0;i<s.size();i++){
      |              ~^~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6480 KB Output is correct
2 Correct 18 ms 6224 KB Output is correct
3 Correct 14 ms 6480 KB Output is correct
4 Correct 22 ms 6224 KB Output is correct
5 Correct 17 ms 6248 KB Output is correct
6 Correct 16 ms 6224 KB Output is correct
7 Correct 22 ms 6112 KB Output is correct
8 Correct 6 ms 4688 KB Output is correct
9 Correct 6 ms 4688 KB Output is correct
10 Correct 12 ms 5712 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 30284 KB Output is correct
2 Correct 183 ms 26556 KB Output is correct
3 Correct 184 ms 30312 KB Output is correct
4 Correct 192 ms 26944 KB Output is correct
5 Correct 241 ms 27580 KB Output is correct
6 Correct 164 ms 21084 KB Output is correct
7 Correct 179 ms 21352 KB Output is correct
8 Correct 73 ms 10832 KB Output is correct
9 Correct 107 ms 15184 KB Output is correct
10 Correct 196 ms 25176 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 973 ms 76208 KB Output is correct
2 Correct 728 ms 57776 KB Output is correct
3 Correct 734 ms 76328 KB Output is correct
4 Correct 813 ms 60072 KB Output is correct
5 Correct 948 ms 73308 KB Output is correct
6 Correct 837 ms 53692 KB Output is correct
7 Correct 711 ms 51636 KB Output is correct
8 Correct 215 ms 19948 KB Output is correct
9 Correct 203 ms 19944 KB Output is correct
10 Correct 720 ms 68020 KB Output is correct
11 Correct 918 ms 76484 KB Output is correct
12 Correct 253 ms 25060 KB Output is correct