Submission #768265

#	Time	Username	Problem	Language	Result	Execution time	Memory
768265		NintsiChkhaidze	Palindromic Partitions (CEOI17_palindromic)	C++17	0 / 100	6 ms	4180 KiB

palindromic

#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define ll long long
#define pii pair <int,int>
#define left (h<<1),l,((l + r)>>1)
#define right ((h<<1)|1),((l+r)>>1) + 1,r
using namespace std;

const int N = 1e6 + 5,mod = 1e9 + 7;

int pwr[N];

signed main (){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	int Q;
	cin>>Q;
	
	int k = 31;
	pwr[0] = 1;
	for (int i = 1; i <= 1000000; i++)
		pwr[i] = (pwr[i - 1] * k) % mod;
		
	for (int i= 1; i <= Q; i++){
		string s;
		cin>>s;
		
		int l = 0,r = s.size() - 1;
		int len = 0,ans=0,h1=0,h2 = 0;
		while (l < r){
			++len;
			h1 = (h1 + pwr[len] * (s[l] - 'a' + 1))%mod;
			h2 = (h2 * k % mod + (s[r] - 'a' + 1)*k) %mod;
			
			if (h1 == h2) {
				ans += 2;
				h1 = h2 = 0;
				len = 0;
			}
			++l,--r;
		}
		
		if (l == r) ++len;
		if (len) ++ans;
		cout<<ans<<endl;
	}
}
/*
1
bonobo
4
bonobo
deleted
racecar
racecars
*/

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