oj.uz

Submission #667183

# Submission time Handle Problem Language Result Execution time Memory
667183 2022-11-30T16:13:24 Z Shahrad Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 108 ms 28524 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define endl '\n'
#define pb push_back
#define mk make_pair
#define sz size()
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define kill(x) return cout << x << endl, void();
#define int ll
#define pii pair <int, int>

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")

const int N = 1e6 + 5;
const int MOD = 998244353, INF = 2e9, sq = 450;

int ps[N], pw[N];
int mab = 27;

int hsh (int l, int r)
{
	return (ps[r] - (l == 0 ? 0 : ps[l - 1]) * pw[r - l + 1] % MOD + MOD) % MOD;
}

void Solve ()
{
	string s;
	cin >> s;
	int n = s.sz, l = 0, ans = 0;
	ps[0] = s[0] - 'a' + 1;
	for (int i = 1; i < n; i++)
			ps[i] = (ps[i - 1] * mab + (s[i] - 'a' + 1)) % MOD;
	for (int r = l; r < n - l; r++)
	{
		if (hsh (l, r) == hsh (n - r - 1, n - l - 1))
		{
			ans += 2;
			if (r == n - l - 1)
				ans--;
			l = r + 1;
		}
	}
	cout << ans << endl;
}

int32_t main ()
{
	pw[0] = 1;
	for (int i = 1; i < N; i++)
		pw[i] = pw[i - 1] * mab % MOD;
	ios::sync_with_stdio (0), cin.tie (0), cout.tie (0);
	int tt = 1;
	cin >> tt;
	while (tt--)
		Solve ();
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8148 KB Output is correct
2 Correct 8 ms 8148 KB Output is correct
3 Correct 9 ms 8116 KB Output is correct
4 Correct 8 ms 8148 KB Output is correct
5 Correct 8 ms 8156 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8148 KB Output is correct
2 Correct 8 ms 8148 KB Output is correct
3 Correct 9 ms 8116 KB Output is correct
4 Correct 8 ms 8148 KB Output is correct
5 Correct 8 ms 8156 KB Output is correct
6 Correct 8 ms 8148 KB Output is correct
7 Correct 8 ms 8148 KB Output is correct
8 Correct 9 ms 8044 KB Output is correct
9 Correct 8 ms 8160 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8148 KB Output is correct
2 Correct 8 ms 8148 KB Output is correct
3 Correct 9 ms 8116 KB Output is correct
4 Correct 8 ms 8148 KB Output is correct
5 Correct 8 ms 8156 KB Output is correct
6 Correct 8 ms 8148 KB Output is correct
7 Correct 8 ms 8148 KB Output is correct
8 Correct 9 ms 8044 KB Output is correct
9 Correct 8 ms 8160 KB Output is correct
10 Correct 10 ms 8240 KB Output is correct
11 Correct 9 ms 8276 KB Output is correct
12 Correct 11 ms 8296 KB Output is correct
13 Correct 8 ms 8252 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8148 KB Output is correct
2 Correct 8 ms 8148 KB Output is correct
3 Correct 9 ms 8116 KB Output is correct
4 Correct 8 ms 8148 KB Output is correct
5 Correct 8 ms 8156 KB Output is correct
6 Correct 8 ms 8148 KB Output is correct
7 Correct 8 ms 8148 KB Output is correct
8 Correct 9 ms 8044 KB Output is correct
9 Correct 8 ms 8160 KB Output is correct
10 Correct 10 ms 8240 KB Output is correct
11 Correct 9 ms 8276 KB Output is correct
12 Correct 11 ms 8296 KB Output is correct
13 Correct 8 ms 8252 KB Output is correct
14 Correct 108 ms 28524 KB Output is correct
15 Correct 64 ms 23424 KB Output is correct
16 Correct 108 ms 27420 KB Output is correct
17 Correct 72 ms 18776 KB Output is correct