Submission #1146806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146806		Mhkhancou	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	306 ms	51320 KiB

palindromic

// In the name of Alah, the most merciful, the most gracious
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define vl vector<ll>
#define mh ios::sync_with_stdio(false); cin.tie(0);
#define tst int t;cin>>t;while(t--)
#define nl '\n'
#define cinv(v) for(auto &it:v)cin>>it;
#define coutv(v) for(auto it:v)cout<<it<<' ';cout<<nl;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define loop(i,a,b) for (int i=a; i <= b; ++i)
#define rev(i, n) for (int i = (n)-1; i >= 0; --i)
#define srt(v) sort(v.begin(),v.end());
#define rsrt(v) sort(v.rbegin(),v.rend());
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define pii pair<int, int>
#define F first
#define S second
#define ld long double
#define no cout << "No\n"
#define yes cout << "Yes\n"
#define dbg(x) cerr << #x << " = " << x << '\n'

const ll N = 2e6 + 5;
const ll INF = LLONG_MAX;
const ll MOD = 1000000007;
const double PI = 2 * acos(0.0);

inline ll gcd(ll a, ll b) { return __gcd(a, b); }
inline ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }



ll BigMod(ll a, ll b, ll M)
{
	ll res = 1;
	a %= M;
	while (b > 0)
	{
		if (b & 1) res = (res * a) % M;
		b >>= 1;
		a = (a * a) % M;
	}
	return res;
}

const int MOD1 = 127657753, MOD2 = 987654319;
const int b1 = 101, b2 = 997;
int inp1, inp2;
pair<int, int> pw[N], inpw[N];
//Template from YouKnowWho and RakibJoy
void precalc()
{
	pw[0] =  {1, 1};
	for (int i = 1; i < N; i++)
	{
		pw[i].first = 1LL * pw[i - 1].first * b1 % MOD1;
		pw[i].second = 1LL * pw[i - 1].second * b2 % MOD2;
	}
	inp2 = BigMod(b2, MOD2 - 2, MOD2);
	inp1 = BigMod(b1, MOD1 - 2, MOD1);
	inpw[0] =  {1, 1};
	for (int i = 1; i < N; i++)
	{
		inpw[i].first = 1LL * inpw[i - 1].first * inp1 % MOD1;
		inpw[i].second = 1LL * inpw[i - 1].second * inp2 % MOD2;
	}

}
struct Hashing
{
	int sz;
	string s; // 0 - indexed string
	vector<pii> hs; // 1 - indexed vector
	Hashing() {}
	Hashing(string _ss)
	{
		sz = _ss.size();
		s = _ss;
		hs.emplace_back(0, 0);
		for (int i = 0; i < sz; i++)
		{
			pii p;
			p.first = (hs[i].first + 1LL * pw[i].first * s[i] % MOD1) % MOD1;
			p.second = (hs[i].second + 1LL * pw[i].second * s[i] % MOD2) % MOD2;
			hs.push_back(p);
		}
	}
	pii get_hash_value(int lo, int hi)   // 1 - indexed
	{
		assert(1 <= lo && lo <= hi && hi <= sz);
		pii ans;
		ans.first = (hs[hi].first - hs[lo - 1].first + MOD1) * 1LL * inpw[lo - 1].first % MOD1;
		ans.second = (hs[hi].second - hs[lo - 1].second + MOD2) * 1LL * inpw[lo - 1].second % MOD2;
		return ans;
	}
	ll hashValue(int l, int r)
	{
		pii h = get_hash_value(l, r);
		return ((ll) h.first << 32) | h.second;
	}
};

void solve()
{
	string s;
	cin >> s;
	Hashing h(s);

	ll ans = 0, last = 1, n = s.size();
	for (int i = 1; i <= n; ++i)
	{
		if (h.get_hash_value(last, i) == h.get_hash_value(n - i + 1, n - last + 1))
		{
			ans ++;
			last = i + 1;
		}
	}

	cout << ans << nl;

}
int main()
{
	mh
	precalc();
	tst
	solve();
	return 0;
}

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