Submission #399399

#	Time	Username	Problem	Language	Result	Execution time	Memory
399399		SavicS	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	112 ms	34628 KiB

palindromic

#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 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40