Submission #1185735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185735		mertbbm	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	242 ms	3252 KiB

palindromic

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

#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<int,pii>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

int mod=1e9;

int f(int a, int b){
	if(a==1||b==0) return 1;
	if(b==1) return a;
	int hold=f((a*a)%mod,b/2);
	if(b%2) hold=(hold*a)%mod;
	return hold;
}

void solve(){
	int n;
	cin >> n;
	for(int x=0;x<n;x++){
		string s;
		cin >> s;
		int l=0;
		int r=s.length()-1;
		int counter2=0;
		int roll=0;
		int ans=0;
		int len=0;
		if(l==r) ans++;
		while(l<r){
			int hold=s[l]-'a';
			int hold2=s[r]-'a';
			roll=(roll*31+hold)%mod;
			counter2=(counter2+(f(31,len)*hold2)%mod)%mod;
			l++;
			r--;
			len++;
			if(roll==counter2){
				ans+=2;
				len=0;
				counter2=0;
				roll=0;
			}
			if(l==r||(l>r&&len)) ans++;
		}
		cout << ans << "\n";
	}
}	
																   
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

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