oj.uz

Submission #100849

# Submission time Handle Problem Language Result Execution time Memory
100849 2019-03-14T21:08:46 Z JedrzejOlkowski Palinilap (COI16_palinilap) C++14
63 / 100
 191 ms 33588 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e5+50;
const ll P1=313LL;
const ll P2=220721LL;
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 1920 KB Output is correct
2 Correct 4 ms 2048 KB Output is correct
3 Correct 4 ms 1980 KB Output is correct
4 Correct 3 ms 1920 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 3456 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 102 ms 33564 KB Output is correct
2 Correct 149 ms 33408 KB Output is correct
3 Correct 127 ms 33436 KB Output is correct
4 Correct 82 ms 33436 KB Output is correct
5 Correct 84 ms 33564 KB Output is correct
6 Correct 95 ms 33436 KB Output is correct
7 Correct 106 ms 33436 KB Output is correct
8 Correct 75 ms 7712 KB Output is correct
9 Correct 87 ms 33436 KB Output is correct
10 Correct 81 ms 33436 KB Output is correct
11 Correct 115 ms 33576 KB Output is correct
12 Correct 105 ms 33436 KB Output is correct
13 Correct 116 ms 33468 KB Output is correct
14 Correct 81 ms 33432 KB Output is correct
15 Correct 85 ms 33464 KB Output is correct
16 Correct 191 ms 33588 KB Output is correct
17 Correct 71 ms 33428 KB Output is correct
18 Correct 99 ms 33400 KB Output is correct
19 Correct 58 ms 33436 KB Output is correct