Submission #939176

# Submission time Handle Problem Language Result Execution time Memory
939176 2024-03-06T06:30:28 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++17
0 / 100
2 ms 1884 KB
#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 = 2e5;
/*
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;

	}
	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;
}
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1884 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1884 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1884 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1884 KB Output isn't correct
2 Halted 0 ms 0 KB -