oj.uz

Submission #37485

# Submission time Handle Problem Language Result Execution time Memory
37485 2017-12-26T02:43:15 Z MatheusLealV Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 166 ms 42168 KB 
#include <bits/stdc++.h>
#define X 145443351LL
#define mod 1000000007LL
using namespace std;
typedef long long ll;

ll Hash[1000010], n, pot[1000010];

inline bool compare(int i, int j, int ii, int jj)
{
	ll dx = (i > 0 ? Hash[i - 1] : 0);

	ll A = (mod + Hash[j] - dx)%mod;

	ll dx2 = (ii > 0 ? Hash[ii - 1] : 0);

	ll A2 = (mod + Hash[jj] - dx2)%mod;

	return (((A*pot[ii])%mod) == ((A2*pot[i])%mod));
}

string s;

int solve(int ini)
{
	int fim = s.size() - 1 - ini;

	if(ini == fim) return 1;

	if(ini > fim) return 0;

	int best = 1;

	for(int p = ini; p <= (ini + fim)/2; p++)
	{
		if(compare(ini, p, fim - p + ini, fim))
		{
			best = max(best, 2 + solve(p + 1));

			break;
		}
	}

	return best;
}

int T;

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>T;

	pot[0] = 1;

	for(int i = 1; i < 1000010; i++) pot[i] = (pot[i - 1]*X)%mod;

	while(T--)
	{
		cin>>s;

		n = s.size();

		Hash[0] = 0;

		for(int i = 0; i < n; i++)
		{
			if(i > 0) Hash[i] = Hash[i - 1];

			Hash[i] = (Hash[i] + s[i]*pot[i])%mod;
		}

		cout<<solve(0)<<"\n";
	}
}

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17800 KB Output is correct
2 Correct 9 ms 17800 KB Output is correct
3 Correct 9 ms 17800 KB Output is correct
4 Correct 6 ms 17800 KB Output is correct
5 Correct 0 ms 17800 KB Output is correct
6 Correct 3 ms 17800 KB Output is correct
7 Correct 9 ms 17800 KB Output is correct
8 Correct 3 ms 17800 KB Output is correct
9 Correct 9 ms 17800 KB Output is correct
10 Correct 9 ms 17908 KB Output is correct
11 Correct 13 ms 17800 KB Output is correct
12 Correct 9 ms 17800 KB Output is correct
13 Correct 9 ms 17800 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17800 KB Output is correct
2 Correct 9 ms 17800 KB Output is correct
3 Correct 9 ms 17800 KB Output is correct
4 Correct 6 ms 17800 KB Output is correct
5 Correct 0 ms 17800 KB Output is correct
6 Correct 3 ms 17800 KB Output is correct
7 Correct 9 ms 17800 KB Output is correct
8 Correct 3 ms 17800 KB Output is correct
9 Correct 9 ms 17800 KB Output is correct
10 Correct 9 ms 17908 KB Output is correct
11 Correct 13 ms 17800 KB Output is correct
12 Correct 9 ms 17800 KB Output is correct
13 Correct 9 ms 17800 KB Output is correct
14 Correct 166 ms 42168 KB Output is correct
15 Correct 83 ms 33632 KB Output is correct
16 Correct 129 ms 19368 KB Output is correct
17 Correct 93 ms 24876 KB Output is correct