oj.uz

Submission #113894

# Submission time Handle Problem Language Result Execution time Memory
113894 2019-05-29T06:08:22 Z Mahdi_Jfri Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 136 ms 20652 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int maxn = 1e6 + 20;
const int mod = 1e9 + 7;
const int base = 6985;

int h[maxn] , pw[maxn];

inline int get(int l , int r)
{
	return (h[r] - (1LL * h[l] * pw[r - l] % mod) + mod) % mod;
}

int getAns(int l , int r)
{
	if(l >= r)
		return 0;
	
	for(int i = 1; i <= r - l; i++)
		if(get(l , l + i) == get(r - i , r))
			return 1 + (i != r - l) + getAns(l + i , r - i);
}

int solve()
{
	string s;
	cin >> s;

	int n = s.size();

	for(int i = 0; i < n; i++)
		h[i + 1] = (1LL * h[i] * base + s[i]) % mod;

	cout << getAns(0 , n) << endl;

	return 0;
}

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

	pw[0] = 1;
	for(int i = 1; i < maxn; i++)
		pw[i] = 1LL * pw[i - 1] * base % mod;

	int t;
	cin >> t;

	while(t--)
		solve();
}

Compilation message

palindromic.cpp: In function 'int getAns(int, int)':
palindromic.cpp:25:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4224 KB Output is correct
2 Correct 11 ms 4096 KB Output is correct
3 Correct 11 ms 4276 KB Output is correct
4 Correct 10 ms 4224 KB Output is correct
5 Correct 10 ms 4224 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4224 KB Output is correct
2 Correct 11 ms 4096 KB Output is correct
3 Correct 11 ms 4276 KB Output is correct
4 Correct 10 ms 4224 KB Output is correct
5 Correct 10 ms 4224 KB Output is correct
6 Correct 10 ms 4272 KB Output is correct
7 Correct 11 ms 4224 KB Output is correct
8 Correct 10 ms 4224 KB Output is correct
9 Correct 10 ms 4224 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4224 KB Output is correct
2 Correct 11 ms 4096 KB Output is correct
3 Correct 11 ms 4276 KB Output is correct
4 Correct 10 ms 4224 KB Output is correct
5 Correct 10 ms 4224 KB Output is correct
6 Correct 10 ms 4272 KB Output is correct
7 Correct 11 ms 4224 KB Output is correct
8 Correct 10 ms 4224 KB Output is correct
9 Correct 10 ms 4224 KB Output is correct
10 Correct 11 ms 4432 KB Output is correct
11 Correct 11 ms 4352 KB Output is correct
12 Correct 11 ms 4480 KB Output is correct
13 Correct 11 ms 4352 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4224 KB Output is correct
2 Correct 11 ms 4096 KB Output is correct
3 Correct 11 ms 4276 KB Output is correct
4 Correct 10 ms 4224 KB Output is correct
5 Correct 10 ms 4224 KB Output is correct
6 Correct 10 ms 4272 KB Output is correct
7 Correct 11 ms 4224 KB Output is correct
8 Correct 10 ms 4224 KB Output is correct
9 Correct 10 ms 4224 KB Output is correct
10 Correct 11 ms 4432 KB Output is correct
11 Correct 11 ms 4352 KB Output is correct
12 Correct 11 ms 4480 KB Output is correct
13 Correct 11 ms 4352 KB Output is correct
14 Correct 136 ms 20652 KB Output is correct
15 Correct 76 ms 15636 KB Output is correct
16 Correct 118 ms 19700 KB Output is correct
17 Correct 79 ms 12944 KB Output is correct