oj.uz

Submission #66104

# Submission time Handle Problem Language Result Execution time Memory
66104 2018-08-09T14:56:28 Z polyfish Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 213 ms 44600 KB 
//I love armpit fetish

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int MAX_N = 1000007;
const int MOD = 1000000007;

int n;
string s;
int64_t H[MAX_N], pw26[MAX_N];

void init() {
	pw26[0] = 1;
	for (int i=1; i<=n; ++i) {
		H[i] = (H[i-1] * 26+ s[i] - 'a') % MOD;
		pw26[i] = pw26[i-1] * 26 % MOD;
	}
}

int64_t get(int l, int r) {
	return (H[r] - H[l-1] * pw26[r-l+1] % MOD + MOD) % MOD;
}

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

int main() {
	//#define OFFLINE_JUDGE doraemon
	#ifdef OFFLINE_JUDGE
		freopen(FILE_NAME".inp", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	int nTest;
	cin >> nTest;
	while (nTest--) {
		cin >> s;
		n = s.size();
		s = '@' + s;
		init();
		//debug(get(1, 2));
		//debug(get(5, 6));
		cout << solve(1, n) << '\n';
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 3 ms 496 KB Output is correct
3 Correct 2 ms 496 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 3 ms 524 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 3 ms 496 KB Output is correct
3 Correct 2 ms 496 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 3 ms 524 KB Output is correct
6 Correct 2 ms 584 KB Output is correct
7 Correct 3 ms 588 KB Output is correct
8 Correct 3 ms 592 KB Output is correct
9 Correct 3 ms 596 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 3 ms 496 KB Output is correct
3 Correct 2 ms 496 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 3 ms 524 KB Output is correct
6 Correct 2 ms 584 KB Output is correct
7 Correct 3 ms 588 KB Output is correct
8 Correct 3 ms 592 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 6 ms 860 KB Output is correct
11 Correct 3 ms 960 KB Output is correct
12 Correct 5 ms 1028 KB Output is correct
13 Correct 5 ms 1268 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 3 ms 496 KB Output is correct
3 Correct 2 ms 496 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 3 ms 524 KB Output is correct
6 Correct 2 ms 584 KB Output is correct
7 Correct 3 ms 588 KB Output is correct
8 Correct 3 ms 592 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 6 ms 860 KB Output is correct
11 Correct 3 ms 960 KB Output is correct
12 Correct 5 ms 1028 KB Output is correct
13 Correct 5 ms 1268 KB Output is correct
14 Correct 213 ms 28420 KB Output is correct
15 Correct 125 ms 33368 KB Output is correct
16 Correct 191 ms 44600 KB Output is correct
17 Correct 125 ms 44600 KB Output is correct