oj.uz

Submission #813421

# Submission time Handle Problem Language Result Execution time Memory
813421 2023-08-07T17:42:31 Z Divane Palinilap (COI16_palinilap) C++14
37 / 100
 74 ms 26700 KB 
/* 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 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;
		ps [i + l - 1]--;
		ps [i]++;
		ps [i - 1]++;
		ps [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];
	int pps = 0;
	int mx = ans;
	for (int i = 0; i < n; 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 += ps[i];
	}
	cout << mx - 1 << '\n';
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 11220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12116 KB Output is correct
2 Correct 9 ms 12056 KB Output is correct
3 Correct 9 ms 12044 KB Output is correct
4 Correct 7 ms 11656 KB Output is correct
5 Correct 8 ms 11916 KB Output is correct
6 Correct 9 ms 12044 KB Output is correct
7 Correct 9 ms 11948 KB Output is correct

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 26700 KB Output isn't correct
2 Halted 0 ms 0 KB -