Submission #247638

#	Time	Username	Problem	Language	Result	Execution time	Memory
247638		emaborevkovic	Palinilap (COI16_palinilap)	C++14	100 / 100	63 ms	25720 KiB

palinilap

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;

#define ff first
#define ss second
#define mp make_pair
#define ll long long
#define pb push_back

const int N = 1e5+11;
const ll baza = 37, MOD = 1e9+7;
string s;
int n;
ll hf[N], hb[N]; 
pair <ll, ll> sweep[N];
ll p[26][N];
ll suma;
ll pot[N];
ll mns[N];

ll add (ll a, ll b) {
	ll ret = a+b;
	if (ret > MOD) ret -= MOD;
	if (ret < 0) ret += MOD;
	return ret;
}

ll mult (ll a, ll b) {
	ll ret = a*b;
	ret %= MOD;
	if (ret < 0) ret += MOD;
	return ret;
}

void hashiranje() {
	hf[0] = (s[0] - 'a' + 1);
	ll mno = baza;
	for (int i=1;i<n;i++) {
		hf[i] = mult (s[i] - 'a' + 1, mno);
		mno = mult(baza, mno);
		hf[i] = add (hf[i], hf[i-1]);
	}
	/////////////////////////////////////////////////
	hb[n-1] = (s[n-1] - 'a' + 1);
	mno = baza;
	for (int i=n-2;i>=0;i--) {
		hb[i] = mult(s[i] - 'a' + 1, mno);
		mno = mult(baza, mno);
		hb[i] = add (hb[i], hb[i+1]);
	}
}

bool jesu (int x1, int y1, int x2, int y2) {
	ll prvi = hf[y1];
	if (x1 > 0) prvi = add(prvi, -hf[x1-1]);
	ll drugi = hb[x2];
	if (y2 < n-1) drugi = add(drugi, -hb[y2+1]);
	int mno1 = y1;
	int mno2 = n-1-x2;
	if (mno1 > mno2) drugi = mult(drugi, pot[mno1-mno2]);
	else prvi = mult(prvi, pot[mno2-mno1]);
	if (prvi == drugi) return 1;
	else return 0;
}

int isti (int x, int y) {
	if (x < 0 || y > n-1) return 0;
	if (s[x] != s[y]) return 0;
	int lo = 0;
	int hi = min(x, n-1-y);
	while (lo < hi) {
		int mid = (lo+hi)/2+1;
		if (jesu(x-mid, x, y, y+mid)) lo = mid;
		else hi = mid-1;
	}
	return lo+1;
}

bool palin (int x, int y) {
	return jesu(x, y, x, y);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> s;
	n = s.size();
	hashiranje();
	pot[0] = 1;
	for (int i=1;i<n;i++) pot[i] = mult(pot[i-1], baza);
	for (int i=0;i<n;i++) {
		int lo = 0;
		int hi = min(i, n-1-i);
		while (lo < hi) {
			int mid = (lo+hi)/2+1;
			if (palin(i-mid, i+mid)) lo = mid;
			else hi = mid-1;
		}
		int r = lo;
		sweep[i-r].ff += 1;
		sweep[i].ff += -1;
		sweep[i].ss += -r;
		if (r > 0) {
			sweep[i+1].ff -= 1;
			sweep[i+1].ss += r+1;
			if (i+r+1 < n) {
				sweep[i+r+1].ff += 1;
				sweep[i+r+1].ss += -1;
			}
		}
		suma += r+1;
		if (i-r-1 < 0 || i+r+1 > n-1) continue;
		int sada = isti(i-r-2, i+r+2);
		p[s[i+r+1] - 'a'][i-r-1] += sada+1;
		p[s[i-r-1] - 'a'][i+r+1] += sada+1;
	}
	/////////////////////////////////////////////////////////////
	for (int i=0;i<n-1;i++) {
		if (s[i] != s[i+1]) {
			int sada = isti(i-1, i+2);
			p[s[i+1]-'a'][i] += sada+1;
			p[s[i]-'a'][i+1] += sada+1;
			continue;
		}
		int lo = 0;
		int hi = min(i, n-1-i-1);
		while (lo < hi) {
			int mid = (lo+hi)/2+1;
			if (palin(i-mid, i+1+mid)) lo = mid;
			else hi = mid-1;
		}
		int r = lo;
		sweep[i-r].ff += 1;
		sweep[i+1].ff -= 1;
		if (r > 0) {
			sweep[i+2].ff -= 1;
			if (i+r+2 < n) sweep[i+r+2].ff += 1;
		}
		if (i+r+2 < n) sweep[i+r+2].ss -= 1;
		suma += r+1;
		if (i-r-1 < 0 || i+r+2 > n-1) continue;
		int sada = isti(i-r-2, i+r+3);
		p[s[i+r+2] - 'a'][i-r-1] += sada+1;
		p[s[i-r-1] - 'a'][i+r+2] += sada+1;
	}
	/////////////////////////////////////////////////////////////
	ll dodaj = 0;
	for (int i=0;i<n;i++) {
		dodaj += sweep[i].ff;
		mns[i] += dodaj;
		if (i > 0) mns[i] += mns[i-1];
		mns[i] += sweep[i].ss;
	//	cout << mns[i] << " ";
	}
	ll poc = suma;
	for (int i=0;i<n;i++) {
		for (int j=0;j<26;j++) {
			if (j == s[i]-'a') continue;
			suma = max(suma, poc + p[j][i] - mns[i]);
		}
	}
	cout << suma;
	return 0;
}

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