Submission #617311

#	Time	Username	Problem	Language	Result	Execution time	Memory
617311		Zanite	Palinilap (COI16_palinilap)	C++17	100 / 100	72 ms	26384 KiB

palinilap

#include <bits/stdc++.h>
using namespace std;

using ll	= long long;

const ll maxN	= 1e5 + 5;
const ll Alph	= 26;

#ifdef Zanite
	#define debug(x) cout << #x << " = " << x << '\n'
#else
	#define debug(x)
#endif

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll getRand(ll l, ll r) {return uniform_int_distribution<ll>(l, r)(rng);}

const ll mod	= 1049433169;
ll madd(ll x, ll y) {x += y; if (x >= mod) x -= mod; return x;}
ll msub(ll x, ll y) {x -= y; if (x < 0) x += mod; return x;}
ll mmul(ll x, ll y) {x *= y; x %= mod; return x;}
ll modexp(ll x, ll y) {
	if (!x) return 0; if (!y) return 1;
	ll t = modexp(x, y >> 1);
	return mmul(t, mmul(t, ((y & 1ll) ? x : 1)));
}

ll key;
ll kpow[maxN], invkpow[maxN];

ll n;

void precomp() {
	key = getRand(1e5, 2e5);

	kpow[0] = invkpow[0] = 1;
	kpow[1] = key, invkpow[1] = modexp(key, mod-2);
	for (ll i = 1; i <= n; i++) {
		kpow[i] = mmul(kpow[i-1], kpow[1]);
		invkpow[i] = mmul(invkpow[i-1], invkpow[1]);
	}
}

struct HashString {
	ll fwd, bwd, len;

	HashString() {fwd = bwd = len = 0;}
	HashString(char c) {
		fwd = bwd = c - 'a';
		len = 1;
	}

	HashString operator + (const HashString &other) const {
		HashString ret = HashString();
		ret.fwd = madd(fwd, mmul(other.fwd, kpow[len]));
		ret.bwd = madd(mmul(bwd, kpow[other.len]), other.bwd);
		ret.len = len + other.len;
		return ret;
	}

	bool isPalindrome() {return (fwd == bwd);}
};

string S;
ll fwd[maxN], bwd[maxN];
ll odd[maxN], even[maxN];
ll change[maxN][Alph];
ll intersect[maxN];

ll getFwd(ll l, ll r) {return mmul(invkpow[l-1], msub(fwd[r], fwd[l-1]));}
ll getBwd(ll l, ll r) {return mmul(invkpow[n-r], msub(bwd[l], bwd[r+1]));}

void computeInitial() {
	// compute forwards and backwards hash
	for (ll i = 1; i <= n; i++) {
		fwd[i] = madd(fwd[i-1], mmul(S[i] - 'a', kpow[i-1]));
	}
	for (ll i = n; i >= 1; i--) {
		bwd[i] = madd(bwd[i+1], mmul(S[i] - 'a', kpow[n-i]));
	}

	// find the number of odd and even palindromes centered at i
	// for even palindromes, the index is the "left part of center"

	// compute intersect[i] := the number of polygons that involve character i
	// because we add slopes, this can be done with prefix prefix difference

	// also, for each center, find the first differing character
	// and find how many palindromes can be created by changing that character

	// odd
	for (ll i = 1; i <= n; i++) {
		ll l = 0, r = min(i-1, n-i), ans = -1;
		while (l <= r) {
			ll m = (l+r) >> 1;
			if (getFwd(i-m, i+m) == getBwd(i-m, i+m)) {
				ans = m;
				l = m + 1;
			} else {
				r = m - 1;
			}
		}
		odd[i] = ans+1;
		intersect[i-ans]++;
		intersect[i+1] -= 2;
		intersect[i+ans+2]++;

		// first different
		ll DL = i-ans-1, DR = i+ans+1;
		if (DL < 1 || DR > n) continue;

		// extend palindrome
		l = 1, r = min(DL-1, n-DR), ans = 0;
		while (l <= r) {
			ll m = (l+r >> 1);
			if (getFwd(DL-m, DL-1) == getBwd(DR+1, DR+m)) {
				ans = m;
				l = m + 1;
			} else {
				r = m - 1;
			}
		}

		change[DL][S[DR] - 'a'] += ans+1;
		change[DR][S[DL] - 'a'] += ans+1;
	}

	// even
	for (ll i = 1; i < n; i++) {
		ll l = 0, r = min(i-1, n-(i+1)), ans = -1;
		while (l <= r) {
			ll m = (l+r) >> 1;
			if (getFwd(i-m, i+m+1) == getBwd(i-m, i+m+1)) {
				ans = m;
				l = m + 1;
			} else {
				r = m - 1;
			}
		}
		even[i] = ans+1;
		intersect[i-ans]++;
		intersect[i+1]--;
		intersect[i+2]--;
		intersect[i+ans+3]++;

		// first different
		ll DL = i-ans-1, DR = i+ans+2;
		if (DL < 1 || DR > n) continue;

		// extend palindrome
		l = 1, r = min(DL-1, n-DR), ans = 0;
		while (l <= r) {
			ll m = (l+r >> 1);
			if (getFwd(DL-m, DL-1) == getBwd(DR+1, DR+m)) {
				ans = m;
				l = m + 1;
			} else {
				r = m - 1;
			}
		}

		change[DL][S[DR] - 'a'] += ans+1;
		change[DR][S[DL] - 'a'] += ans+1;
	}

	// restore the slope slope array as slope array and then as the array
	for (ll i = 1; i <= 2; i++) {
		for (ll j = 1; j < maxN; j++) {
			intersect[j] += intersect[j-1];
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	cin >> S;
	n = S.length();
	S = "#" + S;

	precomp();
	computeInitial();

	// calculate answer if we don't change anything
	ll ans = 0;
	for (ll i = 1; i <= n; i++) {
		ans += odd[i] + even[i];
	}
	debug(ans);

	// compute each possible action that we can take
	ll maxDiff = 0;
	for (ll i = 1; i <= n; i++) {
		for (ll nw = 0; nw < Alph; nw++) {
			if (nw == S[i] - 'a') continue;

			// remove all palindromes with that character as a component, except for odd palindromes
			ll delta = -intersect[i] + odd[i];

			// add all palindromes that will be created
			delta += change[i][nw];

			maxDiff = max(maxDiff, delta);
		}
	}
	cout << ans + maxDiff << '\n';
}

Compilation message (stderr)

palinilap.cpp: In function 'll modexp(ll, ll)':
palinilap.cpp:23:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   23 |  if (!x) return 0; if (!y) return 1;
      |  ^~
palinilap.cpp:23:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   23 |  if (!x) return 0; if (!y) return 1;
      |                    ^~
palinilap.cpp: In function 'void computeInitial()':
palinilap.cpp:115:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  115 |    ll m = (l+r >> 1);
      |            ~^~
palinilap.cpp:153:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  153 |    ll m = (l+r >> 1);
      |            ~^~

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