oj.uz

Submission #464656

# Submission time Handle Problem Language Result Execution time Memory
464656 2021-08-13T15:21:09 Z BERNARB01 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 615 ms 43308 KB 
#include <bits/stdc++.h>

using namespace std;

struct p_hash {
	const int mod = (int) 1e9 + 21;
	const int mod2 = (int) 1e9 + 33;
	const int b = 53;
	const int b2 = 47;
	int n;
	vector<long long> h, h2, pb, pb2;
	p_hash() {}
	p_hash(const string& s) {
		n = s.length();
		h.assign(n + 1, 0);
		h2.assign(n + 1, 0);
		pb.assign(n + 1, 1);
		pb2.assign(n + 1, 1);
		for (int i = 1; i <= n; i++) {
			pb[i] = pb[i - 1] * b % mod;
			pb2[i] = pb2[i - 1] * b2 % mod2;
		}
		for (int i = 0; i < n; i++) {
			h[i + 1] = (h[i] + (s[i] - 'a' + 1) * pb[i]) % mod;
			h2[i + 1] = (h2[i] + (s[i] - 'a' + 1) * pb2[i]) % mod2;
		}
	}
	pair<int, int> get(int l, int r) const {
		return {
			pb[n - l] * (h[r + 1] - h[l] + mod) % mod,
			pb2[n - l] * (h2[r + 1] - h2[l] + mod2) % mod2
		};
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int tt;
	cin >> tt;
	while (tt--) {
		string s;
		cin >> s;
		p_hash sh(s);
		int n = sh.n;
		int l = 0, r = n - 1, ans = 0;
		while (l <= r) {
			int ll = l, rr = r;
			while (1) {
				if (sh.get(l, ll) == sh.get(rr, r)) {
					break;
				}
				ll++;
				rr--;
			}
			if (rr <= ll) {
				ans++;
				break;
			}
			ans += 2;
			l = ll + 1;
			r = rr - 1;
		}
		cout << ans << '\n';
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 6 ms 720 KB Output is correct
11 Correct 4 ms 636 KB Output is correct
12 Correct 6 ms 712 KB Output is correct
13 Correct 5 ms 668 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 6 ms 720 KB Output is correct
11 Correct 4 ms 636 KB Output is correct
12 Correct 6 ms 712 KB Output is correct
13 Correct 5 ms 668 KB Output is correct
14 Correct 615 ms 43308 KB Output is correct
15 Correct 340 ms 38220 KB Output is correct
16 Correct 550 ms 41032 KB Output is correct
17 Correct 312 ms 23288 KB Output is correct