oj.uz

Submission #545191

# Submission time Handle Problem Language Result Execution time Memory
545191 2022-04-03T23:06:44 Z aryan12 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 4761 ms 34764 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e6 + 5, PRIME = 566376197, MOD = 1e9 + 9;
int hash_constant[N], hash_value[N], pref_hash_value[N];
string s;

int power(int a, int b) {
	if(b == 0) {
		return 1;
	}
	if(b == 1) {
		return a % MOD;
	}
	int x = power(a, b / 2);
	x *= x;
	x %= MOD;
	if(b & 1) {
		x *= a;
		x %= MOD;
	}
	return x;
}

int CalcHashValue(int l, int r) {
	int inv = power(power(PRIME, l), MOD - 2);
	int lmao = pref_hash_value[r] - pref_hash_value[l - 1];
	if(lmao < 0) {
		lmao += MOD;
	}
	lmao %= MOD;
	int ans = (lmao * inv) % MOD;
	return ans;
}

int F(int l, int r) {
	if(l > r) {
		return 0;
	}
	if(l == r) {
		return 1;
	}
	int i = l, j = r;
	while(i < j) {
		if(CalcHashValue(l, i) == CalcHashValue(j, r)) {
			return F(i + 1, j - 1) + 2;
		}
		i++, j--;
	}
	return 1;
}

void Solve() {
	cin >> s;
	int n = s.size();
	pref_hash_value[0] = 0;
	for(int i = 1; i <= n; i++) {
		hash_value[i] = (power(PRIME, i) * (s[i - 1] - 'a' + 1)) % MOD;
		pref_hash_value[i] = pref_hash_value[i - 1] + hash_value[i];
		pref_hash_value[i] %= MOD;
		//cout << hash_value[i] << " " << pref_hash_value[i] << "\n";
	}
	cout << F(1, n) << "\n";
}

int32_t main() {
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	for(int i = 0; i < N; i++) {
		hash_constant[i] = power(PRIME, i);
	}
	int t = 1;
	cin >> t;
	while(t--) {
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 8176 KB Output is correct
2 Correct 139 ms 8112 KB Output is correct
3 Correct 140 ms 8148 KB Output is correct
4 Correct 139 ms 8156 KB Output is correct
5 Correct 156 ms 8144 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 8176 KB Output is correct
2 Correct 139 ms 8112 KB Output is correct
3 Correct 140 ms 8148 KB Output is correct
4 Correct 139 ms 8156 KB Output is correct
5 Correct 156 ms 8144 KB Output is correct
6 Correct 143 ms 8280 KB Output is correct
7 Correct 144 ms 8128 KB Output is correct
8 Correct 139 ms 8128 KB Output is correct
9 Correct 158 ms 8120 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 8176 KB Output is correct
2 Correct 139 ms 8112 KB Output is correct
3 Correct 140 ms 8148 KB Output is correct
4 Correct 139 ms 8156 KB Output is correct
5 Correct 156 ms 8144 KB Output is correct
6 Correct 143 ms 8280 KB Output is correct
7 Correct 144 ms 8128 KB Output is correct
8 Correct 139 ms 8128 KB Output is correct
9 Correct 158 ms 8120 KB Output is correct
10 Correct 176 ms 8396 KB Output is correct
11 Correct 162 ms 8348 KB Output is correct
12 Correct 185 ms 8420 KB Output is correct
13 Correct 190 ms 8264 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 8176 KB Output is correct
2 Correct 139 ms 8112 KB Output is correct
3 Correct 140 ms 8148 KB Output is correct
4 Correct 139 ms 8156 KB Output is correct
5 Correct 156 ms 8144 KB Output is correct
6 Correct 143 ms 8280 KB Output is correct
7 Correct 144 ms 8128 KB Output is correct
8 Correct 139 ms 8128 KB Output is correct
9 Correct 158 ms 8120 KB Output is correct
10 Correct 176 ms 8396 KB Output is correct
11 Correct 162 ms 8348 KB Output is correct
12 Correct 185 ms 8420 KB Output is correct
13 Correct 190 ms 8264 KB Output is correct
14 Correct 4761 ms 34764 KB Output is correct
15 Correct 2499 ms 30272 KB Output is correct
16 Correct 4645 ms 34316 KB Output is correct
17 Correct 2612 ms 22248 KB Output is correct