oj.uz

Submission #100848

# Submission time Handle Problem Language Result Execution time Memory
100848 2019-03-14T21:07:32 Z JedrzejOlkowski Palinilap (COI16_palinilap) C++14
63 / 100
 195 ms 33692 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2048 KB Output is correct
2 Correct 4 ms 2048 KB Output is correct
3 Correct 4 ms 1920 KB Output is correct
4 Correct 4 ms 2048 KB Output is correct
5 Correct 4 ms 2048 KB Output is correct

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 3584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 33436 KB Output is correct
2 Correct 128 ms 33564 KB Output is correct
3 Correct 111 ms 33564 KB Output is correct
4 Correct 89 ms 33564 KB Output is correct
5 Correct 97 ms 33568 KB Output is correct
6 Correct 94 ms 33576 KB Output is correct
7 Correct 86 ms 33564 KB Output is correct
8 Correct 81 ms 7708 KB Output is correct
9 Correct 89 ms 33564 KB Output is correct
10 Correct 91 ms 33556 KB Output is correct
11 Correct 123 ms 33520 KB Output is correct
12 Correct 139 ms 33568 KB Output is correct
13 Correct 161 ms 33564 KB Output is correct
14 Correct 96 ms 33564 KB Output is correct
15 Correct 119 ms 33692 KB Output is correct
16 Correct 195 ms 33588 KB Output is correct
17 Correct 53 ms 33564 KB Output is correct
18 Correct 107 ms 33560 KB Output is correct
19 Correct 50 ms 33564 KB Output is correct