Submission #318437

#	Time	Username	Problem	Language	Result	Execution time	Memory
318437		soroush	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	552 ms	35772 KiB

palindromic

/*
#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma,tune=native")
//*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int  ,int > pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn  = 3e6;
const ll mod =1e9+7;
const ll mods [] = {(ll)1e9+7 , (ll)1e9+9 , 696969569 , 177013 , 9699691};
const ld PI = acos((ld)-1);

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

struct hsh{
	string s;
	ll n;
	vector < ll > h;
	vector < ll > p;
	ll base;
	ll mod;
	hsh (string S){
		s = S;
		n = s.size();
		h.reserve(n+100);
		base = rng()%100 + 50;
		mod = mods[rng()%5];
		p.pb(1);
		for(int i = 1 ; i < n + 50 ; i ++)
			p.pb((p.back() * base)%mod);
	}
	void calc(){
		ll cur = 0;
		h.pb(cur);
		for(int i = 0 ; i < n ; i ++){
			cur = (cur * base)%mod;
			cur += s[i] - 'a' + 1;
			cur%=mod;
			h.pb(cur);
		}
	}
	ll get(ll l , ll r){
		ll res = h[r];
		res -= (h[l-1]*p[r-l+1])%mod;
		res%=mod;
		res+=mod;
		return(res%mod);
	}
};

int t;
string s;

int32_t main(){
    migmig;
	cin >> t;
	while(t -- ){
		cin >> s;
		hsh h(s);
		h.calc();
		int n = s.size();
		int l = 1 , r = n ;
		int ans = 0;
		int sum = 0;
		while (r > l){
			bool ok = 0;
			for(int i = l ; i < r ; i ++){
				if(i >= r-i+l)
					break;
				if(h.get(l , i) == h.get(r - i+l , r)){
					ans += 2;
					r = r - i + l-1;
					l = i+1;
					sum = 2*i
;					ok = 1;
					break;
				}
			}
			if(!ok)
				ans ++ , l = r , sum = 2*l;
		}
		if(sum < n)ans++;
		
		cout << ans << endl;
	}




    return(0);
}

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40