Submission #161882

#	Time	Username	Problem	Language	Result	Execution time	Memory
161882		amoo_safar	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	96 ms	20676 KiB

palindromic

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const ll Mod = 998244353;
const ll Inf = 2242545357980376863LL;
const ll Log = 20;
const ll N = 1ll << Log;
const int Maxn = 1e6 + 10;
const int Base = 101;

ll pw[Maxn];

void MAIN(){
	str s;
	cin >> s;
	ll n = s.size();
	ll ans = 0;
	ll l = 0;
	ll h1 = 0, h2 = 0;
	for(int i = 0, j = n - 1; i < n; i++, j--){
		h1 = (h1 * Base + s[i]) % Mod;
		h2 = (h2 + pw[l] * s[j]) % Mod;
		if(h1 == h2){
			ans ++;
			h1 = 0;
			h2 = 0;
			l = 0;
		} else l ++;
	}
	
	cout << ans << '\n';
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	pw[0] = 1;
	for(int i = 1; i < Maxn; i++) pw[i] = (pw[i - 1] * Base) % Mod;
	ll T;
	cin >> T;
	while(T--) MAIN();
	return 0;
}
/*
4
bonobo
deleted
racecar
racecars
*/

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