Submission #1165330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165330		subham_krr	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	205 ms	24204 KiB

palindromic

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

int M = (1e9+7);
int B = 31;
vector<int> power(1, 1);

void precompute_powers(int n) {
    while (power.size() <= n) {
        power.push_back((power.back() * B) % M);
    }
}

vector<int> compute_hash(string s) {
    int n = s.size();
    vector<int> p_hash(n + 1, 0);
    for (int i = 0; i < n; i++) {
        p_hash[i + 1] = ((p_hash[i] * B) % M + s[i]) % M;
    }
    return p_hash;
}

int get_hash(vector<int>& p_hash, int start, int end) {
    int raw_val = (p_hash[end + 1] - (p_hash[start] * power[end - start + 1]) % M);
    return (raw_val % M + M) % M;
}

signed main() {
	int t;
	cin>>t;
	while(t--)
	{
		string s;
		cin>>s;
		int n=s.size();
		precompute_powers(n);
		vector<int>f_hash,b_hash;
		f_hash.push_back(0);
		b_hash.push_back(0);
		int chk=0,ans=0,cut=0;
		for(int i=0;i<n;i++)
		{
			if(i>n-i-1)
			{break;
			}
			f_hash.push_back(((f_hash.back()*B)%M+s[i])%M);
			b_hash.push_back((b_hash.back()+(s[n-i-1]*power[(int)b_hash.size()-1])%M)%M);
			if(f_hash.back()==b_hash.back())
			{ans++;
			chk=1;
			if(i==n-1-i)
			{cut++;
			}
			while((int)b_hash.size()>1)
			{b_hash.pop_back();
			f_hash.pop_back();
			}
			}
			else{chk=0;
			}
		}
		int res=0;
//		cout<<chk<<endl;
if(chk==0)
{res=1;
}
		cout<<2*ans+res-cut<<endl;
		
		
	}
}

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