oj.uz

답안 #100841

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
100841 2019-03-14T20:53:14 Z JedrzejOlkowski Palinilap (COI16_palinilap) C++14
0 / 100
 100 ms 31056 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);
		if( i-d<1 || i+d>n ) continue;
		Plus[i-d][ (int)Wczytaj[i+d]-96 ]+=(ll)(d2+1);
		Plus[i+d][ (int)Wczytaj[i-d]-96 ]+=(ll)(d2+1);
	}
}

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+d+1, n);
			if( i-d<1 || i+d+1>n ) continue;
			
			Plus[i-d][ (int)Wczytaj[i+d+1]-96 ]+=(ll)(d2+1);
			Plus[i+d+1][ (int)Wczytaj[i-d]-96 ]+=(ll)(d2+1);
			continue;
		}
		d=JakDaleko(i-1, i+2, n);
		Plus[i][ (int)Wczytaj[i+1]-96 ]+=(ll)(d+1);
		Plus[i+1][ (int)Wczytaj[i]-96 ]+=(ll)(d+1);
	}
}

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[1] << endl;
	//cout << "plus " << Plus[1][1] << endl;
	cout<< max( Zamiana(n), wynik ) << "\n";
	return 0;
}

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 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 Incorrect 4 ms 1920 KB Output isn't correct

Subtask #2
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 3456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 100 ms 31056 KB Output isn't correct
2 Halted 0 ms 0 KB -