oj.uz

답안 #100850

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
100850 2019-03-14T21:11:07 Z JedrzejOlkowski Palinilap (COI16_palinilap) C++14
63 / 100
 235 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=220721LL;
const ll M=1000LL*1000LL*1000LL+21LL;
const ll M2=1000000007LL;
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)%M2;
	}
}

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] )%M2;	
	}
	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] )%M2;
	}
}

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]+M2)%M2;
	h3=(Hasz1[p2][1]-Hasz1[k2+1][1]+M)%M; h4=(Hasz2[p2][1]-Hasz2[k2+1][1]+M2)%M2; 
	if( p1>n-k2+1 ){
		h3=(h3*Potegi1[ p1-n+k2-1 ])%M;
		h4=(h4*Potegi2[ p1-n+k2-1 ])%M2;
	}
	else{
		h1=(h1*Potegi1[ n-k2+1-p1 ])%M;
		h2=(h2*Potegi2[ n-k2+1-p1 ])%M2;
	}
	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

# 결과 실행 시간 메모리 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 3 ms 1920 KB Output is correct

Subtask #2
0 / 37.0

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

Subtask #3
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 130 ms 33488 KB Output is correct
2 Correct 125 ms 33436 KB Output is correct
3 Correct 138 ms 33488 KB Output is correct
4 Correct 95 ms 33564 KB Output is correct
5 Correct 92 ms 33488 KB Output is correct
6 Correct 101 ms 33564 KB Output is correct
7 Correct 91 ms 33692 KB Output is correct
8 Correct 79 ms 7708 KB Output is correct
9 Correct 81 ms 33436 KB Output is correct
10 Correct 114 ms 33436 KB Output is correct
11 Correct 123 ms 33492 KB Output is correct
12 Correct 122 ms 33428 KB Output is correct
13 Correct 143 ms 33484 KB Output is correct
14 Correct 102 ms 33436 KB Output is correct
15 Correct 129 ms 33484 KB Output is correct
16 Correct 235 ms 33572 KB Output is correct
17 Correct 52 ms 33436 KB Output is correct
18 Correct 98 ms 33376 KB Output is correct
19 Correct 50 ms 33436 KB Output is correct