Submission #100848

#	Time	Username	Problem	Language	Result	Execution time	Memory
100848		JedrzejOlkowski	Palinilap (COI16_palinilap)	C++14	63 / 100	195 ms	33692 KiB

palinilap

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e5+50;
const ll P1=313LL;
const ll P2=137LL;
const ll M=1000LL*1000LL*1000LL+21LL;
char Wczytaj[N];

ll Potegi1[N];
ll Potegi2[N];
ll Hasz1[N][2];
ll Hasz2[N][2];

ll Plus[N][33];
ll Minus[N];
pair<ll, ll>CA[N];
ll wynik=0LL;

void LiczPotegi(){
	Potegi1[0]=Potegi2[0]=1LL;
	for(int i=1; i<N; i++){
		Potegi1[i]=(Potegi1[i-1]*P1)%M;
		Potegi2[i]=(Potegi2[i-1]*P2)%M;
	}
}

void WczytajDane(int &n){
	string slowo;
	getline(cin, slowo);
	n=(int)slowo.size();
	for(int i=1; i<=n; i++) Wczytaj[i]=slowo[i-1];
}

void LiczHasze(int n){
	for(int i=1; i<=n; i++){
		Hasz1[i][0]=( Hasz1[i-1][0]+Potegi1[i]*(ll)Wczytaj[i] )%M;
		Hasz2[i][0]=( Hasz2[i-1][0]+Potegi2[i]*(ll)Wczytaj[i] )%M;	
	}
	for(int i=n; i>=1; i--){
		Hasz1[i][1]=( Hasz1[i+1][1]+Potegi1[n-i+1]*(ll)Wczytaj[i] )%M;
		Hasz2[i][1]=( Hasz2[i+1][1]+Potegi2[n-i+1]*(ll)Wczytaj[i] )%M;
	}
}

int CzyRowne(int p1, int k1, int p2, int k2, int n){
	int h1, h2, h3, h4;
	h1=(Hasz1[k1][0]-Hasz1[p1-1][0]+M)%M; h2=(Hasz2[k1][0]-Hasz2[p1-1][0]+M)%M;
	h3=(Hasz1[p2][1]-Hasz1[k2+1][1]+M)%M; h4=(Hasz2[p2][1]-Hasz2[k2+1][1]+M)%M; 
	if( p1>n-k2+1 ){
		h3=(h3*Potegi1[ p1-n+k2-1 ])%M;
		h4=(h4*Potegi2[ p1-n+k2-1 ])%M;
	}
	else{
		h1=(h1*Potegi1[ n-k2+1-p1 ])%M;
		h2=(h2*Potegi2[ n-k2+1-p1 ])%M;
	}
	if(h1==h3 && h2==h4) return 1;
	return 0;
}

int JakDaleko(int pl, int pp, int n){
	int p, k, s;
	if(pl<1 || pp>n || Wczytaj[pl]!=Wczytaj[pp]) return 0;
	p=1; k=min(pl, n-pp+1);
	while(p<k){
		s=(p+k+1)/2;
		if( CzyRowne(pl-s+1, pl, pp, pp+s-1, n) ) p=s;
		else 						    k=s-1;
	}
	return p;
}

void Dodaj(int p, int k, ll pw, ll roz){
	CA[p].first+=pw;			 CA[p].second+=roz;
	CA[k+1].first-=(pw+(ll)(k-p+1)*roz); CA[k+1].second-=roz;
}

void LiczPalindromyNieparzyste(int n){
	int d, d2;
	Minus[1]++; Minus[n]++;
	wynik+=2LL;
	for(int i=2; i<n; i++){
		d=JakDaleko(i-1, i+1, n)+1;
		wynik+=(ll)d;
		Minus[i]-=(ll)(d-1);
		Dodaj(i-d+1, i, 1LL, 1LL);
		Dodaj(i+1, i+d-1, (ll)(d-1), -1LL);
		d2=JakDaleko(i-d-1, i+d+1, n)+1;
		if( i-d<1 || i+d>n ) continue;
		Plus[i-d][ (int)Wczytaj[i+d]-96 ]+=(ll)d2;
		Plus[i+d][ (int)Wczytaj[i-d]-96 ]+=(ll)d2;
	}
}

void LiczPalindromyParzyste(int n){
	int d, d2;
	for(int i=1; i<n; i++){
		if( Wczytaj[i]==Wczytaj[i+1] ){
			d=JakDaleko(i, i+1, n);
			Dodaj(i-d+1, i, 1LL, 1LL);
			Dodaj(i+1, i+1+d-1, (ll)d, -1LL);
			wynik+=(ll)d;
			d2=JakDaleko(i-d-1, i+1+d+1, n)+1;
			if( i-d<1 || i+d+1>n ) continue;
			Plus[i-d][ (int)Wczytaj[i+d+1]-96 ]+=(ll)d2;
			Plus[i+d+1][ (int)Wczytaj[i-d]-96 ]+=(ll)d2;
			continue;
		}
		d=JakDaleko(i-1, i+2, n)+1;
		Plus[i][ (int)Wczytaj[i+1]-96 ]+=(ll)d;
		Plus[i+1][ (int)Wczytaj[i]-96 ]+=(ll)d;
	}
}

void WyliczCA(int n){
	pair<ll, ll> aktu=make_pair(0LL, 0LL);
	for(int i=1; i<=n; i++){
		aktu.first+=CA[i].first; aktu.second+=CA[i].second;
		Minus[i]+=aktu.first;
		aktu.first+=aktu.second;
	}
}

ll Zamiana(int n){
	ll wynik1=0LL;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=30; j++){
			if( j==(int)Wczytaj[i]-96 ) continue;
			wynik1=max(wynik1, wynik-Minus[i]+Plus[i][j]+1LL);
		}
	}
	return wynik1;
}

int main (){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int n;
	WczytajDane(n);
	LiczPotegi();
	LiczHasze(n);
	LiczPalindromyNieparzyste(n);
	LiczPalindromyParzyste(n);
	WyliczCA(n);
	cout<< max( Zamiana(n), wynik ) << "\n";
	return 0;
}

• Subtask 1: 17 / 17
• Subtask 2: 0 / 37
• Subtask 3: 46 / 46