oj.uz

Submission #243284

# Submission time Handle Problem Language Result Execution time Memory
243284 2020-06-30T19:24:10 Z Lawliet Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 644 ms 17840 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;

const int MAXN = 1000010;

int prime = 31;
int mod = 1000000009;

int n;

lli pot[MAXN];
lli pHash[MAXN];

string s;

int getHash(int L, int R)
{
	lli ans = pHash[R + 1];
	ans -= pHash[L]*pot[R - L + 1];

	ans %= mod;
	if( ans < 0 ) ans += mod;

	return (int)ans;
}

int main()
{
	int t;
	cin >> t;

	pot[0] = 1;

	for(int i = 1 ; i < MAXN ; i++)
		pot[i] = pot[i - 1]*prime, pot[i] %= mod;

	while( t-- )
	{
		cin >> s;
		n = (int)s.size();

		for(int i = 1 ; i <= n ; i++)
		{
			pHash[i] = pHash[i - 1]*prime + s[i - 1] - 'a';
			pHash[i] %= mod;
		}

		int sz = 1, ans = 0;
		int l = 0, r = n - 1;

		while( l <= r )
		{
			sz = 1;

			while( getHash( l , l + sz - 1 ) != getHash( r - sz + 1 , r ) )
				sz++;

			ans++;
			l += sz; r -= sz;

			if( l <= r + 1 ) ans++;
		}

		printf("%d\n",ans);
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8192 KB Output is correct
2 Correct 14 ms 8192 KB Output is correct
3 Correct 15 ms 8192 KB Output is correct
4 Correct 13 ms 8192 KB Output is correct
5 Correct 13 ms 8192 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8192 KB Output is correct
2 Correct 14 ms 8192 KB Output is correct
3 Correct 15 ms 8192 KB Output is correct
4 Correct 13 ms 8192 KB Output is correct
5 Correct 13 ms 8192 KB Output is correct
6 Correct 15 ms 8192 KB Output is correct
7 Correct 15 ms 8192 KB Output is correct
8 Correct 14 ms 8192 KB Output is correct
9 Correct 14 ms 8192 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8192 KB Output is correct
2 Correct 14 ms 8192 KB Output is correct
3 Correct 15 ms 8192 KB Output is correct
4 Correct 13 ms 8192 KB Output is correct
5 Correct 13 ms 8192 KB Output is correct
6 Correct 15 ms 8192 KB Output is correct
7 Correct 15 ms 8192 KB Output is correct
8 Correct 14 ms 8192 KB Output is correct
9 Correct 14 ms 8192 KB Output is correct
10 Correct 21 ms 8192 KB Output is correct
11 Correct 18 ms 8192 KB Output is correct
12 Correct 20 ms 8192 KB Output is correct
13 Correct 18 ms 8192 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8192 KB Output is correct
2 Correct 14 ms 8192 KB Output is correct
3 Correct 15 ms 8192 KB Output is correct
4 Correct 13 ms 8192 KB Output is correct
5 Correct 13 ms 8192 KB Output is correct
6 Correct 15 ms 8192 KB Output is correct
7 Correct 15 ms 8192 KB Output is correct
8 Correct 14 ms 8192 KB Output is correct
9 Correct 14 ms 8192 KB Output is correct
10 Correct 21 ms 8192 KB Output is correct
11 Correct 18 ms 8192 KB Output is correct
12 Correct 20 ms 8192 KB Output is correct
13 Correct 18 ms 8192 KB Output is correct
14 Correct 644 ms 17160 KB Output is correct
15 Correct 355 ms 17840 KB Output is correct
16 Correct 632 ms 17840 KB Output is correct
17 Correct 342 ms 13008 KB Output is correct