Submission #710618

#	Time	Username	Problem	Language	Result	Execution time	Memory
710618		WonderfulWhale	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	46 ms	11044 KiB

palindromic

#include<bits/stdc++.h>
using namespace std;

#define int int64_t
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

const int CNST = 31;
const int MOD = 1e9+7;
int pot[1000009];

int solve(string a) {
	int h1 = 0;
	int h2 = 0;
	int s = 0;
	int e = sz(a)-1;
	int cur = 0;
	int ans = 0;
	int S = 0;
	int E = 0;
	while(s<e) {
		h1 += (a[s]-'a'+1)*pot[cur];
		h1 %= MOD;
		h2 *= CNST;
		h2 += (a[e]-'a'+1);
		h2 %= MOD;
		if(h1==h2) {
			h1 = h2 = cur = 0;
			ans+=2;
			S = s;
			E = e;
		} else {
			cur++;
		}
		s++;
		e--;
	}
	return ans+(S+1!=E);
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	pot[0] = 1;
	for(int i=1;i<1000009;i++) pot[i]=pot[i-1]*CNST%MOD;
	
	int t;
	cin >> t;
	while(t--) {
		string s;
		cin >> s;
		cout << solve(s) << "\n";
	}
}

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