oj.uz

Submission #243283

# Submission time Handle Problem Language Result Execution time Memory
243283 2020-06-30T19:19:58 Z Lawliet Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 832 ms 33328 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;

const int MAXN = 1000010;

int prime[] = { 17 , 31 };
int mod[] = { 1000000007 , 1000000009 };

int n;

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

string s;

int getHash(int L, int R, int p)
{
	L++; R++;

	int sz = R - L + 1;

	lli ans = pHash[R][p];
	ans -= pHash[L - 1][p]*pot[sz][p];

	ans %= mod[p];
	if( ans < 0 ) ans += mod[p];

	return (int)ans;
}

bool areEqual(int L1, int R1, int L2, int R2)
{
	if( getHash( L1 , R1 , 0 ) != getHash( L2 , R2 , 0 ) ) return false;
	if( getHash( L1 , R1 , 1 ) != getHash( L2 , R2 , 1 ) ) return false;
	return true;
}

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

	pot[0][0] = pot[0][1] = 1;

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

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

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

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

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

			while( !areEqual( l , l + sz - 1 , 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 22 ms 16000 KB Output is correct
2 Correct 24 ms 16000 KB Output is correct
3 Correct 23 ms 16000 KB Output is correct
4 Correct 22 ms 16000 KB Output is correct
5 Correct 24 ms 15992 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 16000 KB Output is correct
2 Correct 24 ms 16000 KB Output is correct
3 Correct 23 ms 16000 KB Output is correct
4 Correct 22 ms 16000 KB Output is correct
5 Correct 24 ms 15992 KB Output is correct
6 Correct 23 ms 16000 KB Output is correct
7 Correct 23 ms 16000 KB Output is correct
8 Correct 23 ms 16000 KB Output is correct
9 Correct 24 ms 16000 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 16000 KB Output is correct
2 Correct 24 ms 16000 KB Output is correct
3 Correct 23 ms 16000 KB Output is correct
4 Correct 22 ms 16000 KB Output is correct
5 Correct 24 ms 15992 KB Output is correct
6 Correct 23 ms 16000 KB Output is correct
7 Correct 23 ms 16000 KB Output is correct
8 Correct 23 ms 16000 KB Output is correct
9 Correct 24 ms 16000 KB Output is correct
10 Correct 30 ms 16128 KB Output is correct
11 Correct 27 ms 16256 KB Output is correct
12 Correct 30 ms 16128 KB Output is correct
13 Correct 28 ms 16128 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 16000 KB Output is correct
2 Correct 24 ms 16000 KB Output is correct
3 Correct 23 ms 16000 KB Output is correct
4 Correct 22 ms 16000 KB Output is correct
5 Correct 24 ms 15992 KB Output is correct
6 Correct 23 ms 16000 KB Output is correct
7 Correct 23 ms 16000 KB Output is correct
8 Correct 23 ms 16000 KB Output is correct
9 Correct 24 ms 16000 KB Output is correct
10 Correct 30 ms 16128 KB Output is correct
11 Correct 27 ms 16256 KB Output is correct
12 Correct 30 ms 16128 KB Output is correct
13 Correct 28 ms 16128 KB Output is correct
14 Correct 832 ms 32748 KB Output is correct
15 Correct 423 ms 33328 KB Output is correct
16 Correct 736 ms 33196 KB Output is correct
17 Correct 413 ms 24884 KB Output is correct