Submission #1311702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311702		metalius	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	213 ms	34532 KiB

palindromic

#include "bits/stdc++.h"

using namespace std;

using ll = long long;

#define MAXN 1000003

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

const unsigned long long HMOD1 = rng(); //llabs(rng());
const unsigned long long HMOD2 = rng();//llabs(rng());
const ll ppow = 31;

ll h1[MAXN];
ll h2[MAXN];
ll pows1[MAXN];
ll pows2[MAXN];


void precomp(string & s) {
	
	for(int i = 0; i < s.size(); i++) {
		if(i == 0) {
			h1[i] = (ll)(s[i] - 'a' + 1);
			h2[i] = h1[i];
		} else {
			h1[i] = h1[i-1]*ppow + (ll)(s[i] - 'a' + 1);
			h2[i] = h2[i-1]*ppow + (ll)(s[i] - 'a' + 1);
			h1[i] %= HMOD1;
			h2[i] %= HMOD2;
		}
	}
}

pair<ll,ll> hsh(int a, int b) {
	// s0 s1 s2 s3 s4
	// s2 s3 s4
	if(a == 0) return {h1[b],h2[b]};
	// s4 + s3 * p + s2 * p^2
	// h1[4] = s4 + s3*p + s2*p^2 + s1*p^3 +s0*p^4
	// h1[1] = s1 + s0*p
	// hsh(2,4) = h1[4] - h1[2-1]*p^(4-2+1)
	return {(h1[b] - ((pows1[b-a+1]*h1[a-1]) % HMOD1) + HMOD1) % HMOD1, (h2[b] - ((pows2[b-a+1]*h2[a-1]) % HMOD2) + HMOD2) % HMOD2};
}

bool eq(int a1, int b1, int a2, int b2) {
	auto hh1 = hsh(a1,b1);
	auto hh2 = hsh(a2,b2);
	return hh1.first == hh2.first && hh1.second == hh2.second;
}



ll qr(int a, int b,int mdind) {
	if(a > b) return 0;
	if(a == b) return 1;
	if(a == b-1) return eq(a,a,b,b)?2:1; 
	for(int i = a,j=b; i <= mdind; i++,j--) {
		if(eq(a,i,j,b)) return 2 + qr(i+1,j-1,mdind);
	} 
	return 1;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	pows1[0] = 1;
	pows2[0] = 1;
	for(int i = 1; i <= (int)(1e6); i++) {
		pows1[i] = pows1[i-1]*ppow;
		pows2[i] = pows2[i-1]*ppow;
		pows1[i] %= HMOD1;
		pows2[i] %= HMOD2;
	}
	int t; cin >> t;
	while(t--) {
		string s; cin >> s;
		precomp(s);
		if(s.size() == 1) {
			cout << 1 << "\n";
			continue;
		}
		cout << qr(0,s.size() - 1,((int)s.size() - 1)/2) << "\n";
	}
	return 0;
}

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