oj.uz

Submission #797710

# Submission time Handle Problem Language Result Execution time Memory
797710 2023-07-29T19:34:07 Z IBory Palindromes (APIO14_palindrome) C++17
73 / 100
 321 ms 31360 KB 
#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;

const ll MAX = 300003, MOD1 = 998244353, MOD2 = 846545669;
char C[MAX];
int P[MAX];
ll D[2][MAX], IP[2][MAX], ans;
map<ll, ll> cnt, Z;
map<ll, vector<ll>> G;

ll Pow(ll N, ll K, const ll MOD) {
	ll ret = 1;
	while (K) {
		if (K & 1) ret = ret * N % MOD;
		N = N * N % MOD;
		K >>= 1LL;
	}
	return ret;
}

ll Hash(int L, int R) {
	if (L > R) return -1;
	R++;
	ll a = (D[0][R] - D[0][L] + MOD1) * IP[0][L] % MOD1;
	ll b = (D[1][R] - D[1][L] + MOD2) * IP[1][L] % MOD2;
	return (a << 31LL) + b;
}

ll DFS(ll cur) {
	ll n = cnt[cur];
	for (ll next : G[cur]) n += DFS(next);
	ans = max(ans, n * Z[cur]);
	return n;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	string A, B;
	cin >> A;
	for (char c : A) {
		B.push_back(c);
		B.push_back('_');
	}
	B.pop_back();

	int N = A.size(), M = B.size();
	D[0][0] = D[1][0] = IP[0][0] = IP[1][0] = 1;
	ll p1 = 1, p2 = 1, ip1 = Pow(313, MOD1 - 2, MOD1), ip2 = Pow(479, MOD2 - 2, MOD2);
	for (int i = 0; i < N; ++i) {
		C[i] = A[i];
		D[0][i + 1] = (D[0][i] + C[i] * p1) % MOD1;
		D[1][i + 1] = (D[1][i] + C[i] * p2) % MOD2;
		IP[0][i + 1] = IP[0][i] * ip1 % MOD1;
		IP[1][i + 1] = IP[1][i] * ip2 % MOD2;
		p1 = p1 * 313 % MOD1;
		p2 = p2 * 479 % MOD2;
	}
	
	int R = -1, K = -1;
	for (int i = 0; i < M; ++i) {
		if (i <= R) P[i] = min(R - i, P[2 * K - i]);
		while (i - P[i] - 1 >= 0 && i + P[i] + 1 < M && B[i - P[i] - 1] == B[i + P[i] + 1]) P[i]++;
		if (R < i + P[i]) R = i + P[i], K = i;
	}

	for (int i = 0; i < M; ++i) {
		int l = i - P[i], r = i + P[i];
		if (l & 1) l++;
		if (r & 1) r--;
		if (l > r) continue;
		l >>= 1, r >>= 1;
		ll pv = 0, cur = Hash(l, r), cut = Z.find(cur) != Z.end();
		cnt[cur]++;
		Z[cur] = r - l + 1;
		do {
			if (pv) G[cur].push_back(pv);
			if (cut) break;
			pv = cur;
			l++; r--;
			if (l <= r) {
				cur = Hash(l, r);
				if (Z.find(cur) != Z.end()) cut = 1;
				else Z[cur] = r - l + 1;
			}
		} while (l <= r);
		if (l > r) G[0].push_back(cur);
	}

	DFS(0);
	cout << ans;
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 328 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 324 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 1 ms 324 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 1 ms 324 KB Output is correct
31 Correct 0 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 2 ms 584 KB Output is correct
6 Correct 1 ms 580 KB Output is correct
7 Correct 1 ms 580 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 584 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3412 KB Output is correct
2 Correct 13 ms 3284 KB Output is correct
3 Correct 15 ms 3456 KB Output is correct
4 Correct 15 ms 3324 KB Output is correct
5 Correct 10 ms 3392 KB Output is correct
6 Correct 15 ms 3340 KB Output is correct
7 Correct 13 ms 3148 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 2 ms 852 KB Output is correct
10 Correct 7 ms 2516 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 31328 KB Output is correct
2 Correct 307 ms 29948 KB Output is correct
3 Correct 321 ms 31360 KB Output is correct
4 Correct 318 ms 30104 KB Output is correct
5 Correct 213 ms 30392 KB Output is correct
6 Correct 170 ms 22868 KB Output is correct
7 Correct 243 ms 25132 KB Output is correct
8 Correct 11 ms 4896 KB Output is correct
9 Correct 46 ms 10912 KB Output is correct
10 Correct 170 ms 26572 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 24824 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -