oj.uz

Submission #713474

# Submission time Handle Problem Language Result Execution time Memory
713474 2023-03-22T07:55:08 Z Astrayt Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 114 ms 20620 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define int ll
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair

int pw[1000005], P = 41, mod = 998244353;

void solve(){
	string s; cin >> s;
	int n = s.size(), i = 0, j = n - 1, cur_sz = 0, ans = 0;
	int lh = 0, rh = 0;
	while(j - i > 0){
		lh = (lh * P % mod + s[i] % mod);
		rh = (rh + pw[cur_sz] * s[j]) % mod;
		cur_sz++;
		if(lh == rh){
			cur_sz = lh = rh = 0;
			ans += 2;
		}
		i++, j--;
	}
	if(cur_sz != 0 || n % 2) ans++;
	cout << ans << '\n';
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	pw[0] = 1;
	for(int i = 1; i <= 1000000; ++i) pw[i] = pw[i - 1] * P % mod;
	int t = 1; cin >> t;
	while(t--) solve();
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8080 KB Output is correct
2 Correct 10 ms 8148 KB Output is correct
3 Correct 9 ms 8068 KB Output is correct
4 Correct 10 ms 8020 KB Output is correct
5 Correct 9 ms 8144 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8080 KB Output is correct
2 Correct 10 ms 8148 KB Output is correct
3 Correct 9 ms 8068 KB Output is correct
4 Correct 10 ms 8020 KB Output is correct
5 Correct 9 ms 8144 KB Output is correct
6 Correct 9 ms 8148 KB Output is correct
7 Correct 10 ms 8148 KB Output is correct
8 Correct 9 ms 8148 KB Output is correct
9 Correct 10 ms 8052 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8080 KB Output is correct
2 Correct 10 ms 8148 KB Output is correct
3 Correct 9 ms 8068 KB Output is correct
4 Correct 10 ms 8020 KB Output is correct
5 Correct 9 ms 8144 KB Output is correct
6 Correct 9 ms 8148 KB Output is correct
7 Correct 10 ms 8148 KB Output is correct
8 Correct 9 ms 8148 KB Output is correct
9 Correct 10 ms 8052 KB Output is correct
10 Correct 10 ms 8276 KB Output is correct
11 Correct 9 ms 8216 KB Output is correct
12 Correct 10 ms 8160 KB Output is correct
13 Correct 10 ms 8148 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8080 KB Output is correct
2 Correct 10 ms 8148 KB Output is correct
3 Correct 9 ms 8068 KB Output is correct
4 Correct 10 ms 8020 KB Output is correct
5 Correct 9 ms 8144 KB Output is correct
6 Correct 9 ms 8148 KB Output is correct
7 Correct 10 ms 8148 KB Output is correct
8 Correct 9 ms 8148 KB Output is correct
9 Correct 10 ms 8052 KB Output is correct
10 Correct 10 ms 8276 KB Output is correct
11 Correct 9 ms 8216 KB Output is correct
12 Correct 10 ms 8160 KB Output is correct
13 Correct 10 ms 8148 KB Output is correct
14 Correct 103 ms 20620 KB Output is correct
15 Correct 63 ms 15520 KB Output is correct
16 Correct 114 ms 19688 KB Output is correct
17 Correct 62 ms 14744 KB Output is correct