oj.uz

Submission #100845

# Submission time Handle Problem Language Result Execution time Memory
100845 2019-03-14T21:05:07 Z JedrzejOlkowski Palinilap (COI16_palinilap) C++14
63 / 100
 163 ms 31388 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][30];
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]-=(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<=26; 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 << "wynik " << wynik << endl;
	//cout << "minus " << Minus[2] << endl;
	//cout << "plus " << Plus[2][2] << endl;
	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 1920 KB Output is correct
3 Correct 4 ms 1920 KB Output is correct
4 Correct 4 ms 1920 KB Output is correct
5 Correct 4 ms 1920 KB Output is correct

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3328 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 93 ms 31176 KB Output is correct
2 Correct 102 ms 31260 KB Output is correct
3 Correct 108 ms 31260 KB Output is correct
4 Correct 82 ms 31132 KB Output is correct
5 Correct 97 ms 31132 KB Output is correct
6 Correct 80 ms 31132 KB Output is correct
7 Correct 102 ms 31232 KB Output is correct
8 Correct 78 ms 7856 KB Output is correct
9 Correct 90 ms 31264 KB Output is correct
10 Correct 84 ms 31260 KB Output is correct
11 Correct 133 ms 31388 KB Output is correct
12 Correct 120 ms 31132 KB Output is correct
13 Correct 163 ms 31260 KB Output is correct
14 Correct 83 ms 31260 KB Output is correct
15 Correct 80 ms 31132 KB Output is correct
16 Correct 147 ms 31132 KB Output is correct
17 Correct 47 ms 31260 KB Output is correct
18 Correct 98 ms 31132 KB Output is correct
19 Correct 81 ms 31132 KB Output is correct