Submission #869352

#	Time	Username	Problem	Language	Result	Execution time	Memory
869352		serifefedartar	Palinilap (COI16_palinilap)	C++17	0 / 100	27 ms	12888 KiB

palinilap

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+9;
const ll LOGN = 30; 
const ll MAXN = 1e5 + 100;
const ll MULT = 1e9;

const ll P = 31;
string s;
int decr[MAXN], inc[26][MAXN], n;
ll hashes[MAXN], hashes_rev[MAXN], pw[MAXN], res = 0;
ll _hash(int x, int len, bool rev) {
	if (rev == 0) {
		int r = x + len - 1;
		ll res = (hashes[r] - (hashes[x-1] * pw[r-x+1]) % MOD + MOD) % MOD;
		return res;
	} else {
		int l = x - len + 1;
		ll res = (hashes_rev[l] - (hashes_rev[x+1] * pw[x+1-l]) % MOD + MOD) % MOD;
		return res;
	}
}

void f(int l, int r, int v) {
	decr[l] += v;
	decr[r+1] -= v;
}

void calc(int x, int y) {
	int mx_len = x;
	int L = 1;
	int R = mx_len;
	int ans = 0;
	while (R >= L) {
		int mid = L + (R-L)/2;
		if (_hash(x, mid, 1) == _hash(y, mid, 0)) {
			ans = mid;
			L = mid + 1;
		} else
			R = mid - 1;
	}

	if (ans < 1)
		return ;
	res += ans; 

	int l = x - ans + 1;
	int r = x + ans - 1;
	if (x != y) {
		f(l, r, 1);
		int L = l-1;
		int R = r+1;
		if (L != 0 && R != n+1) {
			inc[s[L] - 'a'][R]++;
			inc[s[R] - 'a'][L]++;
		}
	} else {
		f(l, x-1, 1);
		f(x+1, r, 1);
		int L = l-1;
		int R = r+1;
		if (L != 0 && R != n+1) {
			inc[s[L] - 'a'][R]++;
			inc[s[R] - 'a'][L]++;
		}
	}
}

int main() {
	fast
	cin >> s;
	n = s.length();
	s = "#" + s;
	pw[0] = 1;
	for (int i = 1; i < MAXN; i++)
		pw[i] = (pw[i-1] * P) % MOD;
	for (int i = 1; i <= n; i++)
		hashes[i] = hashes[i-1] * P + (s[i] - 'a' + 1);		
	for (int i = n; i >= 1; i--)
		hashes_rev[i] = hashes_rev[i+1] * P + (s[i] - 'a' + 1);

	for (int i = 1; i <= n; i++) {
		calc(i, i);
		if (i != 1)
			calc(i-1, i);
	}

	for (int i = 1; i <= n; i++)
		decr[i] += decr[i-1];

	ll ans = res;
	cout << "res= " << res << "\n";
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 26; j++)
			ans = max(ans, res + inc[j][i] - decr[i]);
	}
	cout << ans << "\n";
}

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