제출 #813466

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
813466		Divane	Palinilap (COI16_palinilap)	C++14	100 / 100	86 ms	31420 KiB

palinilap

/* In the name of GOD */

#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second 
#define mk make_pair
typedef long long ll;
typedef long double ld;
#define int long long
typedef pair <int, int> pii;
const int N = 200012, M = 1000000007, B = 373;
int a[N], b[N];
int ps[N];
int pe[N];
int A[26];
int hr[N];
int hl[N];
int p[N];
int n;
vector <int> st[N], e[N];
int sp[N], sn[N];

int getL (int l, int r) {
	l = n - 1 - l;
	r = n - 1 - r;
	return (((hl[r] - hl[l - 1] * p[r - l + 1]) % M) + M) % M;
}

int getR (int l, int r) {
	return (((hr[r] - hr[l - 1] * p[r - l + 1]) % M) + M) % M;
}

int32_t main () {
	p[0] = 1;
	for (int i = 1; i < N; i++) {
		p[i] = p[i - 1] * B;
		p[i] %= M;
	}
	string s, t;
	cin >> t;
	s = "#3#4#";
	for (char c : t) {
		s += c;
		s += '#';
	}
	s += "2#1#";
	n = (int)s.size();
	int H = 0;
	for (int i = 0; i < n; i++) {
		H *= B;
		H += s[i];
		H %= M;
		hr[i] = H;
	}
	reverse(s.begin(), s.end());
	H = 0;
	for (int i = 0; i < n; i++) {
		H *= B;
		H += s[i];
		H %= M;
		hl[i] = H;
	}
	reverse(s.begin(), s.end());
	int ans = 0;
	for (int i = 5; i < n - 5; i++) {
		int l = 1, r = min(i, n - i - 1);
		while (r - l > 1) {
			int mid = (l + r) >> 1;
			if (getR (i, i + mid - 1) == getL(i, i - mid + 1))
				l = mid;
			else
				r = mid;
		}
		st[i - l].push_back(i);
		e[i + l].push_back(i);
		ans += (l / 2);
		a[i] = l / 2;
		if (l != 1) {
			ps [i + l - 1]--;
			ps [i]++;
			sn [i + l - 1]--;
			sn [i]++;
			ps [i - 1]++;
			ps [i - l]--;
			sp [i - 1]++;
			sp [i - l]--;
		}
		int ol = l + 1;
		l = 0, r = min(n - (i + ol) - 1, i - ol);
		while (r - l > 1) {
			int mid = (l + r) >> 1;
			if (getR (i + ol, i + ol + mid - 1) == getL(i - ol, i - ol - mid + 1))
				l = mid;
			else
				r = mid;
		}
		b[i] = l;
	}
	for (int i = n - 1; i >= 0; i--)
		ps[i] = ps[i + 1] + ps[i];
	for (int i = n - 1; i >= 0; i--)
		sp[i] = sp[i + 1] + sp[i];
	for (int i = n - 1; i >= 0; i--)
		sn[i] = sn[i + 1] + sn[i];
	int pps = 0;
	int mx = ans + 1;
	for (int i = 0; i < n; i++) {
		if (i % 2)
			pps += sp[i];
		if (i >= 5 && i < n - 5 && i % 2) {
			int ANS = ans;
			ANS -= pps;
			ANS += a[i];
			for (int wef : st[i]) {
				char c = s[wef + (wef - i)];
				A[c - 'a'] += b[wef] / 2 + 1;
			}
			for (int wef : e[i]) {
				char c = s[wef - (i - wef)];
				A[c - 'a'] += b[wef] / 2 + 1;
			}
			int MX = 0;
			for (int i = 0; i < 26; i++) {
				MX = max(MX, A[i]);
				A[i] = 0;
			}
			mx = max(mx, MX + ANS);
		}
		if (i % 2)
			pps += sn[i];
	}
	cout << mx - 1 << '\n';
}

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