Submission #104889

#	Time	Username	Problem	Language	Result	Execution time	Memory
104889		Shtef	Palinilap (COI16_palinilap)	C++14	54 / 100	181 ms	21116 KiB

palinilap

#include <iostream>

using namespace std;

typedef long long ll;

string s;
int n, cnt1[100005], cnt2[100005], kolko[100005][30];
ll frbr[100005], bcbr[100005], frsum[100005], bcsum[100005], b[100005];
ll frh1[100005], frh2[100005], bch1[100005], bch2[100005], pot1[100005], pot2[100005];
const ll mod = (ll)1e9 + 7;
const ll B1 = 100003LL;
const ll B2 = 13337LL;

bool same(int prvix, int prviy, int drugix, int drugiy){
	if((frh1[prviy] - (frh1[prvix - 1] * pot1[prviy - prvix + 1]) % mod + mod) % mod != (bch1[drugiy] - (bch1[drugix + 1] * pot1[drugix - drugiy + 1]) % mod + mod) % mod)
		return 0;
	if((frh2[prviy] - (frh2[prvix - 1] * pot2[prviy - prvix + 1]) % mod + mod) % mod != (bch2[drugiy] - (bch2[drugix + 1] * pot2[drugix - drugiy + 1]) % mod + mod) % mod)
		return 0;
	return 1;
}

ll brojpalin(){
	ll ret = 0;
	for(int i = 1 ; i <= n ; ++i){
		int l = 0, r = min(i - 1, n - i);
		while(l < r){
			int mid = (l + r + 1) / 2;
			if(same(i - mid, i - 1, i + mid, i + 1)){
				l = mid;
			}
			else{
				r = mid - 1;
			}
		}
		ret += l + 1;
		int x = i - l, y = i + l;
		//cout << x << ' ' << i << " - " << y << ' ' << i << " : " << l << endl;
		frbr[x]++;
		frbr[i]--;
		bcbr[y]++;
		bcbr[i]--;
		frsum[i] -= l;
		bcsum[i] -= l;
		x--;
		y++;
		if(x <= 0 || y > n)
			continue;
		int poc = l;
		r = min(i - 1, n - i);
		l = min(r, l + 1);
		//cout << l << " - : - " << r << ".-." << poc << endl;
		while(l < r){
			int mid = (l + r + 1) / 2;
			//cout << mid << "::" << same(i - mid, i - poc - 2, i + mid, i + poc + 2) << endl;
			if(same(i - mid, i - poc - 2, i + mid, i + poc + 2)){
				l = mid;
			}
			else{
				r = mid - 1;
			}
		}
		int cnt = l - poc;
		//cout << i << ' ' << l << ' ' << poc << endl;
		kolko[x][s[y - 1] - 'a'] += cnt;
		kolko[y][s[x - 1] - 'a'] += cnt;
	}
	for(int i = 1 ; i < n ; ++i){
		int l = -1, r = min(i - 1, n - i - 1);
		while(l < r){
			int mid = (l + r + 1) / 2;
			if(same(i - mid, i, i + mid + 1, i + 1)){
				l = mid;
			}
			else{
				r = mid - 1;
			}
		}
		ret += l + 1;
		int x = i - l, y = i + l + 1;
		//cout << x << ' ' << i + 1 << " - " << y << ' ' << i << " : " << l << endl;
		frbr[x]++;
		frbr[i + 1]--;
		bcbr[y]++;
		bcbr[i]--;
		frsum[i + 1] -= (l + 1);
		bcsum[i] -= (l + 1);
		x--;
		y++;
		if(x <= 0 || y > n)
			continue;
		int poc = l;
		r = min(i - 1, n - i - 1);
		l = min(r, l + 1);
		while(l < r){
			int mid = (l + r + 1) / 2;
			if(same(i - mid, i - poc - 2, i + mid + 1, i + poc + 3)){
				l = mid;
			}
			else{
				r = mid - 1;
			}
		}
		//cout << endl;
		int cnt = l - poc;
		kolko[x][s[y - 1] - 'a'] += cnt;
		kolko[y][s[x - 1] - 'a'] += cnt;
	}
	return ret;
}

void inithash(){
	for(int i = 1 ; i <= n ; ++i){
		frh1[i] = (frh1[i - 1] * B1 + s[i - 1] - 'a' + 1) % mod;
		frh2[i] = (frh2[i - 1] * B2 + s[i - 1] - 'a' + 1) % mod;
	}
	for(int i = n ; i >= 1 ; --i){
		bch1[i] = (bch1[i + 1] * B1 + s[i - 1] - 'a' + 1) % mod;
		bch2[i] = (bch2[i + 1] * B2 + s[i - 1] - 'a' + 1) % mod;
	}
	pot1[0] = pot2[0] = 1;
	for(int i = 1 ; i <= n ; ++i){
		pot1[i] = (pot1[i - 1] * B1) % mod;
		pot2[i] = (pot2[i - 1] * B2) % mod;
	}
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> s;
n = (int)s.size();
inithash();
ll sve = brojpalin();
ll sad = 0, cnt = 0;
for(int i = 1 ; i <= n ; ++i){
	//cout << frbr[i] << ' ';
	cnt += frbr[i];
	sad += frsum[i];
	sad += cnt;
	b[i] += sad;
	//cout << b[i] << ' ';
}
//cout << endl;
sad = 0;
cnt = 0;
for(int i = n ; i >= 1 ; --i){
	cnt += bcbr[i];
	sad += bcsum[i];
	sad += cnt;
	b[i] += sad;
}
/*
for(int i = 1 ; i <= n ; ++i){
	cout << b[i] << ' ';
}
*/
ll sol = sve;
//cout << sol << endl;
for(int i = 1 ; i <= n ; ++i){
	ll maxi = 0;
	for(int j = 0 ; j < 26 ; ++j){
		if(j == s[i - 1] - 'a')
			continue;
		maxi = max(maxi, (ll)kolko[i][j]);
	}
	sol = max(sol, sve - b[i] + maxi);
}
cout << sol << endl;

return 0;
}

• Subtask 1: 17 / 17
• Subtask 2: 37 / 37
• Subtask 3: 0 / 46