oj.uz

Submission #1086948

# Submission time Handle Problem Language Result Execution time Memory
1086948 2024-09-11T19:48:19 Z ZeroCool Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 50 ms 28172 KB 
#include <bits/stdc++.h>

using namespace std;

#define ar array
#define int long long
#define ld long double
#define crash assert(69 == 420)

const int MOD = 1e9 + 7;
const int INF = 1e17;
const int N = 2e6  + 20;
const int LOG = 20;

const int B = 954285419; //! Pray to RNGesus for no collisions

int pw[N];

signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
	int t;
	cin>>t;
	pw[0] = 1;
	for(int i = 1;i < N;i++)pw[i] = (pw[i - 1] * B) % MOD;
	while(t--){
		string s;
		cin>>s;
		int n = s.size();
		int ans = 0;
		int l = 0, r = n - 1;
		int x = 0, y = 0, sz = 0;
		while(l < r){
			x = (x * B + s[l] ) % MOD;
			y = (y + pw[sz] * s[r] ) % MOD;
			if(x == y){
				x = y = sz = 0;
				ans += 2;
			}else sz++;
			l++, r--;
		}
		if(n % 2 || sz)ans++;
		cout<<ans<<'\n';
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15964 KB Output is correct
2 Correct 15 ms 15960 KB Output is correct
3 Correct 17 ms 15964 KB Output is correct
4 Correct 16 ms 16220 KB Output is correct
5 Correct 14 ms 16076 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15964 KB Output is correct
2 Correct 15 ms 15960 KB Output is correct
3 Correct 17 ms 15964 KB Output is correct
4 Correct 16 ms 16220 KB Output is correct
5 Correct 14 ms 16076 KB Output is correct
6 Correct 15 ms 15964 KB Output is correct
7 Correct 15 ms 15964 KB Output is correct
8 Correct 15 ms 15964 KB Output is correct
9 Correct 14 ms 15964 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15964 KB Output is correct
2 Correct 15 ms 15960 KB Output is correct
3 Correct 17 ms 15964 KB Output is correct
4 Correct 16 ms 16220 KB Output is correct
5 Correct 14 ms 16076 KB Output is correct
6 Correct 15 ms 15964 KB Output is correct
7 Correct 15 ms 15964 KB Output is correct
8 Correct 15 ms 15964 KB Output is correct
9 Correct 14 ms 15964 KB Output is correct
10 Correct 15 ms 16220 KB Output is correct
11 Correct 15 ms 15964 KB Output is correct
12 Correct 15 ms 16032 KB Output is correct
13 Correct 15 ms 15964 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15964 KB Output is correct
2 Correct 15 ms 15960 KB Output is correct
3 Correct 17 ms 15964 KB Output is correct
4 Correct 16 ms 16220 KB Output is correct
5 Correct 14 ms 16076 KB Output is correct
6 Correct 15 ms 15964 KB Output is correct
7 Correct 15 ms 15964 KB Output is correct
8 Correct 15 ms 15964 KB Output is correct
9 Correct 14 ms 15964 KB Output is correct
10 Correct 15 ms 16220 KB Output is correct
11 Correct 15 ms 15964 KB Output is correct
12 Correct 15 ms 16032 KB Output is correct
13 Correct 15 ms 15964 KB Output is correct
14 Correct 47 ms 28172 KB Output is correct
15 Correct 36 ms 23516 KB Output is correct
16 Correct 50 ms 27504 KB Output is correct
17 Correct 32 ms 22516 KB Output is correct