oj.uz

Submission #939179

# Submission time Handle Problem Language Result Execution time Memory
939179 2024-03-06T06:31:50 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++17
60 / 100
 52 ms 28980 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;
		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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1884 KB Output is correct
2 Correct 2 ms 1884 KB Output is correct
3 Correct 2 ms 1884 KB Output is correct
4 Correct 2 ms 1832 KB Output is correct
5 Correct 2 ms 1880 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1884 KB Output is correct
2 Correct 2 ms 1884 KB Output is correct
3 Correct 2 ms 1884 KB Output is correct
4 Correct 2 ms 1832 KB Output is correct
5 Correct 2 ms 1880 KB Output is correct
6 Correct 2 ms 1884 KB Output is correct
7 Correct 2 ms 1880 KB Output is correct
8 Correct 2 ms 1884 KB Output is correct
9 Correct 2 ms 2020 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1884 KB Output is correct
2 Correct 2 ms 1884 KB Output is correct
3 Correct 2 ms 1884 KB Output is correct
4 Correct 2 ms 1832 KB Output is correct
5 Correct 2 ms 1880 KB Output is correct
6 Correct 2 ms 1884 KB Output is correct
7 Correct 2 ms 1880 KB Output is correct
8 Correct 2 ms 1884 KB Output is correct
9 Correct 2 ms 2020 KB Output is correct
10 Correct 3 ms 2140 KB Output is correct
11 Correct 2 ms 2140 KB Output is correct
12 Correct 3 ms 2040 KB Output is correct
13 Correct 3 ms 2188 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1884 KB Output is correct
2 Correct 2 ms 1884 KB Output is correct
3 Correct 2 ms 1884 KB Output is correct
4 Correct 2 ms 1832 KB Output is correct
5 Correct 2 ms 1880 KB Output is correct
6 Correct 2 ms 1884 KB Output is correct
7 Correct 2 ms 1880 KB Output is correct
8 Correct 2 ms 1884 KB Output is correct
9 Correct 2 ms 2020 KB Output is correct
10 Correct 3 ms 2140 KB Output is correct
11 Correct 2 ms 2140 KB Output is correct
12 Correct 3 ms 2040 KB Output is correct
13 Correct 3 ms 2188 KB Output is correct
14 Runtime error 52 ms 28980 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -