oj.uz

Submission #399399

# Submission time Handle Problem Language Result Execution time Memory
399399 2021-05-05T16:43:06 Z SavicS Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 112 ms 34628 KB 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1000005;
const int inf = 1e9 + 5;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

int n;
string s;

const int mod = 1e9 + 7;
ll add(ll a, ll b){
	a += b;
	if(a >= mod)a -= mod;
	return a;
}
ll sub(ll a, ll b){
	a -= b;
	if(a < 0)a += mod;
	return a;
}
ll mul(ll a, ll b){
	return (a * b) % mod;
}
ll power(ll a, ll b){
	if(!b)return 1;
	ll pola = power(a, b / 2);
	pola = mul(pola, pola);
	if(b % 2 == 1)pola = mul(pola, a);
	return pola;
}
ll inv(ll a){
	return power(a, mod - 2);
}

const int p = 31;
ll pw[maxn];
ll invz[maxn];

void init_hsh(){
	pw[0] = 1;
	ff(i,1,maxn - 1)pw[i] = mul(pw[i - 1], p);
	invz[maxn - 1] = inv(pw[maxn - 1]);
	fb(i,maxn - 2,0)invz[i] = mul(invz[i + 1], p);	
}

ll hsh[maxn];
ll get(int l, int r){
	if(l > r)return 0;
	return mul(sub(hsh[r], hsh[l - 1]), invz[l - 1]);
}

void Solve(){
	cin >> s;
	n = sz(s);
	
	ff(i,0,n - 1)hsh[i + 1] = add(hsh[i], mul(s[i] - 'a' + 1, pw[i]));
	
	int br = 0;
	int l = 1, r = n;
	while(l <= r){
		
		ff(i,l,r){
			if(get(l, i) == get(r - (i - l + 1) + 1, r)){
				br += (i == r ? 1 : 2);
				r = r - (i - l + 1);
				l = i + 1;
				break;
			}
		}
		
	}
	
	cout << br << endl;

}

int main()
{
   	ios::sync_with_stdio(false);
   	cout.tie(nullptr);
  	cin.tie(nullptr);
  	init_hsh();
	int t = 1;
	cin >> t;
	while(t--)Solve();
   	return 0;
}
/**

bonobo
deleted

// probati bojenje sahovski ili slicno

**/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15948 KB Output is correct
2 Correct 18 ms 15980 KB Output is correct
3 Correct 17 ms 15948 KB Output is correct
4 Correct 17 ms 15908 KB Output is correct
5 Correct 17 ms 15948 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15948 KB Output is correct
2 Correct 18 ms 15980 KB Output is correct
3 Correct 17 ms 15948 KB Output is correct
4 Correct 17 ms 15908 KB Output is correct
5 Correct 17 ms 15948 KB Output is correct
6 Correct 17 ms 15976 KB Output is correct
7 Correct 17 ms 15984 KB Output is correct
8 Correct 17 ms 15948 KB Output is correct
9 Correct 17 ms 15948 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15948 KB Output is correct
2 Correct 18 ms 15980 KB Output is correct
3 Correct 17 ms 15948 KB Output is correct
4 Correct 17 ms 15908 KB Output is correct
5 Correct 17 ms 15948 KB Output is correct
6 Correct 17 ms 15976 KB Output is correct
7 Correct 17 ms 15984 KB Output is correct
8 Correct 17 ms 15948 KB Output is correct
9 Correct 17 ms 15948 KB Output is correct
10 Correct 18 ms 16076 KB Output is correct
11 Correct 18 ms 16076 KB Output is correct
12 Correct 18 ms 16180 KB Output is correct
13 Correct 18 ms 16076 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15948 KB Output is correct
2 Correct 18 ms 15980 KB Output is correct
3 Correct 17 ms 15948 KB Output is correct
4 Correct 17 ms 15908 KB Output is correct
5 Correct 17 ms 15948 KB Output is correct
6 Correct 17 ms 15976 KB Output is correct
7 Correct 17 ms 15984 KB Output is correct
8 Correct 17 ms 15948 KB Output is correct
9 Correct 17 ms 15948 KB Output is correct
10 Correct 18 ms 16076 KB Output is correct
11 Correct 18 ms 16076 KB Output is correct
12 Correct 18 ms 16180 KB Output is correct
13 Correct 18 ms 16076 KB Output is correct
14 Correct 112 ms 34628 KB Output is correct
15 Correct 69 ms 30012 KB Output is correct
16 Correct 105 ms 34100 KB Output is correct
17 Correct 70 ms 25960 KB Output is correct