Submission #320494

#	Time	Username	Problem	Language	Result	Execution time	Memory
320494		MahdiBahramian	Palindromic Partitions (CEOI17_palindromic)	C++11	100 / 100	233 ms	44188 KiB

palindromic

#include<bits/stdc++.h>
#define pb push_back
#define ins insert
#define var auto
#define F first
#define S second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int Mod1 = 1e9 + 7;
const int Mod2 = 1e9 + 21;
const int BASE = 37;
const int Max = 1e6 + 10;

ll h1[Max];
ll pw1[Max];
ll h2[Max];
ll pw2[Max];

bool check(int l , int r , int x , int y)
{
	r++ , y++;
	ll f1 = (h1[r] - h1[l] * pw1[r - l] % Mod1 + Mod1) % Mod1;
	ll f2 = (h2[r] - h2[l] * pw2[r - l] % Mod2 + Mod2) % Mod2;
	ll g1 = (h1[y] - h1[x] * pw1[y - x] % Mod1 + Mod1) % Mod1;
	ll g2 = (h2[y] - h2[x] * pw2[y - x] % Mod2 + Mod2) % Mod2;
	return f1 == g1 && f2 == g2;
}

void solve()
{
	string s; cin >> s;
	int n = s.size();
	pw1[0] = pw2[0] = 1;
	for(int i = 1; i <= n ; i++)
	{
		h1[i] = (h1[i - 1] * BASE + s[i - 1]) % Mod1;
		h2[i] = (h2[i - 1] * BASE + s[i - 1]) % Mod2;
		pw1[i] = pw1[i - 1] * BASE % Mod1;
		pw2[i] = pw2[i - 1] * BASE % Mod2;
	}

	int cnt = 0;
	int L = 0 , R = n - 1;
	for(int l = L , r = R ; l < r ; l++ , r--)
	{
		if(check(L , l , r , R))
		{
			//cout << "*" << l - L + 1 << '\n';
			L = l + 1;
			R = r - 1;
			cnt += 2;
		}
	}
	if(L <= R)
		cnt++;
	cout << cnt << '\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t;cin >> t;
	while(t--)
		solve();
}

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