oj.uz

Submission #320587

# Submission time Handle Problem Language Result Execution time Memory
320587 2020-11-09T07:42:49 Z AmShZ Palindromic Partitions (CEOI17_palindromic) C++11
100 / 100
 691 ms 42612 KB 
# include <bits/stdc++.h>
 
/*
// ordered_set 
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
# define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
*/
 
using namespace std;
 
typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;
 
# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
# define InTheNameOfGod                                  ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
 
ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}
 
const int xn = 1e6 + 10;
const int xm = - 20 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const int mod[3] = {998244353, 1000000007, 1000000009};
const int base = 257;

int n, pw[3][xn], Hash[3][xn], inv[3][xn], Inv[3], ans, q;
string s;

void build(){
	for (int i = 0; i < 3; ++ i)
		pw[i][0] = inv[i][0] = 1, Inv[i] = power(base, mod[i] - 2, mod[i]);
	for (int i = 0; i < 3; ++ i){
		for (int j = 1; j < xn; ++ j){
			pw[i][j] = ll(pw[i][j - 1]) * ll(base) % mod[i];
			inv[i][j] = ll(inv[i][j - 1]) * ll(Inv[i]) % mod[i];
		}
	}
}
void build_query(){
	for (int i = 0; i < 3; ++ i)
		for (int j = 1; j <= n; ++ j)
			Hash[i][j] = (ll(Hash[i][j - 1]) + ll(s[j] - 'a') * ll(pw[i][j]) % mod[i]) % mod[i];
}
int get(int l, int r, int ind){
	return (ll(Hash[ind][r]) - ll(Hash[ind][l - 1]) + ll(mod[ind])) * ll(inv[ind][l - 1]) % mod[ind];
}
bool check(int l1, int r1, int l2, int r2){
	bool flag = true;
	for (int i = 0; i < 3; ++ i)
		flag &= get(l1, r1, i) == get(l2, r2, i);
	return flag;
}
void solve(){
	cin >> s;
	n = SZ(s);
	s = '.' + s;
	build_query();
	ans = 0;
	int l = 1, r = 1;
	while (true){
		int l2 = n - r + 1;
		int r2 = n - l + 1;
		if (l2 <= r)
			break;
		if (!check(l, r, l2, r2)){
			++ r;
			continue;
		}
		ans += 2;
		++ r;
		l = r;
		if (n % 2 == 0 && r == n / 2 + 1)
			-- ans;
	}
	++ ans;
	cout << ans << endl;
}

int main(){
	InTheNameOfGod;
	
	build();
	cin >> q;
	while (q --)
		solve();
	
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 23908 KB Output is correct
2 Correct 60 ms 23780 KB Output is correct
3 Correct 60 ms 23800 KB Output is correct
4 Correct 60 ms 23832 KB Output is correct
5 Correct 61 ms 23780 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 23908 KB Output is correct
2 Correct 60 ms 23780 KB Output is correct
3 Correct 60 ms 23800 KB Output is correct
4 Correct 60 ms 23832 KB Output is correct
5 Correct 61 ms 23780 KB Output is correct
6 Correct 61 ms 23780 KB Output is correct
7 Correct 60 ms 23780 KB Output is correct
8 Correct 60 ms 23908 KB Output is correct
9 Correct 62 ms 23780 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 23908 KB Output is correct
2 Correct 60 ms 23780 KB Output is correct
3 Correct 60 ms 23800 KB Output is correct
4 Correct 60 ms 23832 KB Output is correct
5 Correct 61 ms 23780 KB Output is correct
6 Correct 61 ms 23780 KB Output is correct
7 Correct 60 ms 23780 KB Output is correct
8 Correct 60 ms 23908 KB Output is correct
9 Correct 62 ms 23780 KB Output is correct
10 Correct 66 ms 24036 KB Output is correct
11 Correct 64 ms 24040 KB Output is correct
12 Correct 70 ms 24036 KB Output is correct
13 Correct 66 ms 24036 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 23908 KB Output is correct
2 Correct 60 ms 23780 KB Output is correct
3 Correct 60 ms 23800 KB Output is correct
4 Correct 60 ms 23832 KB Output is correct
5 Correct 61 ms 23780 KB Output is correct
6 Correct 61 ms 23780 KB Output is correct
7 Correct 60 ms 23780 KB Output is correct
8 Correct 60 ms 23908 KB Output is correct
9 Correct 62 ms 23780 KB Output is correct
10 Correct 66 ms 24036 KB Output is correct
11 Correct 64 ms 24040 KB Output is correct
12 Correct 70 ms 24036 KB Output is correct
13 Correct 66 ms 24036 KB Output is correct
14 Correct 691 ms 40520 KB Output is correct
15 Correct 392 ms 41872 KB Output is correct
16 Correct 684 ms 42612 KB Output is correct
17 Correct 405 ms 35556 KB Output is correct