Submission #1086948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086948		ZeroCool	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	50 ms	28172 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;

#define ar array
#define int long long
#define ld long double
#define crash assert(69 == 420)

const int MOD = 1e9 + 7;
const int INF = 1e17;
const int N = 2e6  + 20;
const int LOG = 20;

const int B = 954285419; //! Pray to RNGesus for no collisions

int pw[N];

signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
	int t;
	cin>>t;
	pw[0] = 1;
	for(int i = 1;i < N;i++)pw[i] = (pw[i - 1] * B) % MOD;
	while(t--){
		string s;
		cin>>s;
		int n = s.size();
		int ans = 0;
		int l = 0, r = n - 1;
		int x = 0, y = 0, sz = 0;
		while(l < r){
			x = (x * B + s[l] ) % MOD;
			y = (y + pw[sz] * s[r] ) % MOD;
			if(x == y){
				x = y = sz = 0;
				ans += 2;
			}else sz++;
			l++, r--;
		}
		if(n % 2 || sz)ans++;
		cout<<ans<<'\n';
	}
}

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