oj.uz

Submission #320619

# Submission time Handle Problem Language Result Execution time Memory
320619 2020-11-09T09:19:48 Z woldis4 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 3402 ms 18204 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int XN = 1e6+7, md = 1e9+7, base = 257;

ll t, n, p[XN], pw[XN];
string s;

ll tavan(ll a, ll b){
	if (b == 0)	return 1;
	ll adad = tavan(a, b/2);
	return (adad*adad % md) * max(1LL, (b%2)*a) % md;
}

ll substr(int L, int R){
	if (L == 0)	return p[R];
	return ((p[R]-p[L-1]+md) % md) * tavan(pw[L], md-2) % md;
}

void pre(){
	p[0] = int(s[0]);
	for (int i = 1; i < n; ++i)	p[i] = p[i-1] + pw[i]*ll(s[i]), p[i] %= md;
}

int main(){
	cin >> t;
	pw[0] = 1;
	for (int i = 1; i < XN; ++i)	pw[i] = (pw[i-1]*base)%md;
	while (t--){
		cin >> s;
		n = s.size();
		pre();
		ll L = 0, R = n-1, cnt1 = 0, cnt2 = n-1, ans = 0;
		ll flg = 1;
		while (R > L){
			if (substr(cnt1, L) == substr(R, cnt2)){
				if (n%2 == 0 && L == n/2-1 && R == n/2)	flg = 0;
				cnt1 = L+1, cnt2 = R-1, ans += 2;
			}
			++L, R--;
		}
		cout << ans+flg << '\n';
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8172 KB Output is correct
2 Correct 9 ms 8172 KB Output is correct
3 Correct 9 ms 8172 KB Output is correct
4 Correct 10 ms 8172 KB Output is correct
5 Correct 9 ms 8172 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8172 KB Output is correct
2 Correct 9 ms 8172 KB Output is correct
3 Correct 9 ms 8172 KB Output is correct
4 Correct 10 ms 8172 KB Output is correct
5 Correct 9 ms 8172 KB Output is correct
6 Correct 10 ms 8172 KB Output is correct
7 Correct 10 ms 8172 KB Output is correct
8 Correct 10 ms 8172 KB Output is correct
9 Correct 12 ms 8172 KB Output is correct
10 Correct 41 ms 8300 KB Output is correct
11 Correct 26 ms 8300 KB Output is correct
12 Correct 45 ms 8300 KB Output is correct
13 Correct 39 ms 8300 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8172 KB Output is correct
2 Correct 9 ms 8172 KB Output is correct
3 Correct 9 ms 8172 KB Output is correct
4 Correct 10 ms 8172 KB Output is correct
5 Correct 9 ms 8172 KB Output is correct
6 Correct 10 ms 8172 KB Output is correct
7 Correct 10 ms 8172 KB Output is correct
8 Correct 10 ms 8172 KB Output is correct
9 Correct 12 ms 8172 KB Output is correct
10 Correct 41 ms 8300 KB Output is correct
11 Correct 26 ms 8300 KB Output is correct
12 Correct 45 ms 8300 KB Output is correct
13 Correct 39 ms 8300 KB Output is correct
14 Correct 3136 ms 17752 KB Output is correct
15 Correct 1354 ms 18204 KB Output is correct
16 Correct 3402 ms 18088 KB Output is correct
17 Correct 1908 ms 13592 KB Output is correct