oj.uz

Submission #305138

# Submission time Handle Problem Language Result Execution time Memory
305138 2020-09-22T15:45:25 Z miss_robot Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 110 ms 26900 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("O3")
#define int long long

using namespace std;

const int N = 1e6, A = 987361726, B = 1e9+7;
int t, n, l, sol;
int h[N], p[N];
string s;

void pre(){
	h[0] = s[0];
	p[0] = 1;
	for(int i = 1; i < n; i++){
		h[i] = (h[i-1] * A + s[i]) % B;
		p[i] = (p[i-1] * A) % B;
	}
}

int hsh(int a, int b){
	if(!a) return h[b];
	return (h[b] - h[a-1] * p[b-a+1] + B*B) % B;
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cin >> t;
	while(t--){
		cin >> s;
		n = s.size();
		pre();
		l = sol = 0;
		for(int i = 0; i < n/2; i++){
			if(hsh(l, i) == hsh(n-i-1, n-l-1)){
				sol+=2;
				l = i+1;
			}
		}
		if(n%2 || l < n/2) sol++;
		cout << sol << "\n";
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 1 ms 640 KB Output is correct
12 Correct 2 ms 640 KB Output is correct
13 Correct 1 ms 512 KB Output is correct
14 Correct 110 ms 26900 KB Output is correct
15 Correct 59 ms 22292 KB Output is correct
16 Correct 106 ms 26256 KB Output is correct
17 Correct 60 ms 14356 KB Output is correct