Submission #138866

#	Time	Username	Problem	Language	Result	Execution time	Memory
138866		parsa_mobed	Palinilap (COI16_palinilap)	C++14	100 / 100	273 ms	80504 KiB

palinilap

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int N = 1e5 + 10, B = 101, MOD = 1e9 + 7, X = 11;
int Hash[N], revHash[N], P[N], s[N], q[N], Q1[N], Q2[N], ps1[N], ps2[N], n, cnt = 0;
vector <int> V[N][26];

//functions
int mod(int a) {return (a % MOD + MOD) % MOD;}

int HASH(int l, int r)
{
	if (l == 0) return Hash[r];
	return mod(Hash[r] - Hash[l - 1] * P[r - l + 1]);
}

int REVHASH(int l, int r)
{
	return mod(revHash[l] - revHash[r + 1] * P[r - l + 1]);
}

int val(int l1, int r1, int l2, int r2)
{
	if (l1 < 0 || l2 < 0 || r1 >= n || r2 >= n) return 0;
   return (REVHASH(l1, r1) == HASH(l2, r2));
}

int BS(int l1, int l2)
{
	if (l1 < 0 || l2 < 0 || l1 >= n || l2 >= n) return -1;
	if (s[l1] != s[l2]) return -1;
	int L = 0, R = min(l1, n - l2 - 1) + 1;
	while (R - L > 1) {
		int md = (R + L) / 2;
		if (val(l1 - md, l1, l2, l2 + md)) L = md;
		else R = md;
	}
	return L;
}
//end


int32_t main()
{
	//preprocess
	P[0] = 1;
	for (int i = 1; i < N; i ++) P[i] = (P[i - 1] * B) % MOD;
   //Input
	string st; cin >> st;
	n = st.size();
	for (int i = 0; i < n; i ++) s[i] = st[i] - 'a';
	//set Hash
	Hash[0] = s[0] + X;
	for (int i = 1; i < n; i ++) {
		Hash[i] = (Hash[i - 1] * B + s[i] + X) % MOD;
	}
	revHash[n - 1] = s[n - 1] + X;
	for (int i = n - 2; i >= 0; i --) {
		revHash[i] = (revHash[i + 1] * B + s[i] + X) % MOD;
	}
	//end
   for (int i = 0; i < n; i ++) {
		int t = BS(i, i);
		if (i - t - 1 >= 0) V[i - t - 1][s[i + t + 1]].push_back(i + t + 1);
		if (i + t + 1 < n) V[i + t + 1][s[i - t - 1]].push_back(i - t - 1);
		if (t != 0) {
			ps1[i]--;
			ps1[i + t]++;
			Q1[i] = -t;
		}
		if (t != 0) {
			ps2[i]--;
			ps2[i - t]++;
			Q2[i] = -t;
		}
		cnt += t + 1;
	}
	for (int i = 0; i < n - 1; i ++) {
		int t = BS(i, i + 1);
		if (i - t - 1 >= 0) V[i - t - 1][s[i + t + 2]].push_back(i + t + 2);
		if (i + t + 2 < n) V[i + t + 2][s[i - t - 1]].push_back(i - t - 1);
		if (t == -1) continue;
		ps1[i]--;
		ps1[i + t + 1]++;
		Q1[i] += -(t + 1);
		ps2[i + 1]--;
		ps2[i - t]++;
		Q2[i + 1] += -(t + 1);
		cnt += t + 1;
	}
	for (int i = n - 2; i >= 0; i --) ps1[i] += ps1[i + 1];
	for (int i = 1; i < n; i ++) ps2[i] += ps2[i - 1];
	Q1[n - 1] += ps1[n - 1];
	for (int i = n - 2; i >= 0; i --) Q1[i] += ps1[i] + Q1[i + 1];
	Q2[0] += ps2[0];
	for (int i = 1; i < n; i ++) Q2[i] += ps2[i] + Q2[i - 1];
	for (int i = 0; i < n; i ++) q[i] = Q1[i] + Q2[i];
	//find ans
	int ans = cnt;
	for (int i = 0; i < n; i ++) for (int c = 0; c < 26; c ++){
		int val = 0;
		for (auto j : V[i][c]) {
			if (j < 0 || j >= n) continue ;
			if (i < j) val += BS(i - 1, j + 1) + 2;
			else val += BS(j - 1, i + 1) + 2;
		}
		ans = max(ans, cnt + val - q[i]);
	}
   //Output
   cout << ans << "\n";
}

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