Submission #1113947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113947		KarolZ	Palindromes (APIO14_palindrome)	C++17	73 / 100	1054 ms	78568 KiB

palindrome

#include<bits/stdc++.h>
#include<unordered_map>
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 (stderr)

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

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