Submission #939316

#	Time	Username	Problem	Language	Result	Execution time	Memory
939316		iskhakkutbilim	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	130 ms	27456 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define int long long
const int mod = 1e9 + 7;
const int p = 31;
const int N = 2e6;
/*
4
bonobo
deleted
racecar
racecars
*/

int pw[N+10];


void solve(){
	string s; cin >> s;
	int n = s.size();
	
	vector<int> hash(n, 0);
	hash[0] = s[0];
	for(int i = 1;i < n; i++){
		hash[i] = (hash[i-1] * p + s[i]) % mod;
	}
	
	auto get=[&](int l, int r){
		if(l == 0) return hash[r];
		int sum = hash[r] - (pw[r-l+1] * hash[l-1]);
		sum = ((sum % mod) + mod) % mod;
		return sum;
	};
	
	
	
	deque<char> dq;
	for(int i = 0;i < n; i++) dq.push_back(s[i]);
	int left = 0, right = n-1;
	int ans = 0;
	while(true){
		int len = -1;
		for(int j = right; j >= 0; j--){
			if(left + right - j >= j) break;
			/*cout << j+1 << " " << right + 1 << '\n';
			cout << left + 1 << ' ' << left + right - j + 1 << "\n";
			cout << get(j, right) << ' ' << get(left, left+(right-j)) << '\n';
			* */
			if(get(j, right) == get(left, left+(right-j))){
				len = (right-j+1);
				break;
			}
		}
		
		if(len == -1){
			ans++;
			break;
		}
		
		ans+= 2;
		if(dq.empty()) break;
		left+= len, right-= len;
		if(right < left) break;

	}
	cout << ans;
}


signed main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	pw[0] = 1;
	for(int i = 1;i <= N; i++){
		pw[i] = (pw[i-1] * p) % mod;
	}
	int tt; cin >> tt;
	while(tt--){
		solve();
		cout << '\n';
	}
	return 0;
}

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