Submission #617217

#	Time	Username	Problem	Language	Result	Execution time	Memory
617217		Zanite	Palinilap (COI16_palinilap)	C++17	17 / 100	428 ms	524288 KiB

palinilap

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

using ll	= long long;

const int maxN	= 5005;
const int Alph	= 26;

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 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 ans;
ll initPalindrome[maxN][maxN], oddPalindrome[maxN];
ll diffChar[maxN][maxN], diagDiff[maxN][maxN];
ll change[maxN][Alph];

void computeInitial() {
	for (int i = 1; i <= n; i++) {
		HashString H = HashString();
		for (int j = i; j <= n; j++) {
			H = H + HashString(S[j]);
			initPalindrome[i][j] = H.isPalindrome();
			ans += initPalindrome[i][j];
		}
	}

	// compute odd palindromes whose center is i
	for (int c = 1; c <= n; c++) {
		for (int d = 0; c-d >= 1 && c+d <= n; d++) {
			oddPalindrome[c] += initPalindrome[c-d][c+d];
		}
	}
	
	// compute some sort of prefsum for initPalindrome
	for (int i = 1; i <= n; i++) {
		for (int j = n; j >= 1; j--) {
			initPalindrome[i][j] += initPalindrome[i-1][j] + initPalindrome[i][j+1] - initPalindrome[i-1][j+1];
		}
	}

	// calculate whether characters at (i, j) are different or not
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			diffChar[i][j] = (S[i] != S[j]);
		}
	}

	// also calculate some sort of diagonal sum
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			diagDiff[i][j] = diagDiff[i-1][j+1] + diffChar[i][j];
			//cout << diagDiff[i][j] << ' ';
		}
		//cout << '\n';
	}
}

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

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

	precomp();
	computeInitial();

	// find for each substring l..r, on which character can it be changed so that it can be a palindrome
	for (int l = 1; l <= n; l++) {
		for (int r = l; r <= n; r++) {
			ll total = diagDiff[r][l] - diagDiff[l-1][r+1];
			if (total != 2) continue;

			//cout << l << ' ' << r << '\n';

			// binary search different position
			int _L = l, _R = r, dpos = -1;
			while (_L <= _R) {
				int _M = (_L + _R) >> 1;

				if (diagDiff[_M][l+r-_M] - diagDiff[l-1][r+1] >= 1) {
					dpos = _M;
					_R = _M - 1;
				} else {
					_L = _M + 1;
				}
			}

			// insert to change array
			int dpos2 = l+r-dpos;
			change[dpos][S[dpos2] - 'a']++;
			change[dpos2][S[dpos] - 'a']++;

			//for (ll i = l; i <= r; i++) {cout << S[i];}
			//cout << '\n';
		}
	}

	// finally, compute each possible action that we can take
	ll maxDiff = 0;
	for (int i = 1; i <= n; i++) {
		for (int nw = 0; nw < Alph; nw++) {
			//cout << "change[" << i << "][" << nw << "] = " << change[i][nw] << '\n';

			if (nw == S[i] - 'a') continue;

			// remove all palindromes with that character as a component, except for odd palindromes
			ll delta = -initPalindrome[i][i] + oddPalindrome[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:16:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   16 |  if (!x) return 0; if (!y) return 1;
      |  ^~
palinilap.cpp:16:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   16 |  if (!x) return 0; if (!y) return 1;
      |                    ^~

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