oj.uz

Submission #982695

# Submission time Handle Problem Language Result Execution time Memory
982695 2024-05-14T16:12:51 Z Alebn Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 349 ms 48080 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

int n, M = 1e9+7, P = 31, N = 1e6 + 1;
string s;
vector<int> p, inv, haah;

int mod(int i) {
    return (i + M) % M;
}
int fast(int i, int j) {
    //cout << i << " " << j << "\n";
    if(j == 0) return 1;
    int a = fast(i, j / 2);
    return mod(mod(a * a) * (j % 2 == 0 ? 1 : i));
}

signed main() {
    int t;
    cin >> t;
    //
    p = vector<int>(N), inv = vector<int>(N);
    p[0] = 1;
    for(int i = 1; i < N; i++) p[i] = mod(p[i - 1] * P);
    inv[N - 1] = fast(p[N - 1], M - 2);
    for(int i = N - 2; i > -1; i--) inv[i] = mod(inv[i + 1] * P);
    //
    while(t--) {
        cin >> s;
        n = s.size(), haah = vector<int>(n);
        for(int i = 0; i < n; i++) {
            haah[i] = mod((s[i] - 'a') * p[i]);
            if(i != 0) haah[i] = mod(haah[i - 1] + haah[i]);
            //cout << haah[i] << " ";
        }
        //
        int res = 0, last = 0, a, b;
        bool flag = false;
        for(int i = 0; i < n / 2; i++) {
            a = mod(haah[i] - (last == 0 ? 0 : haah[last - 1]));
            a = mod(a * inv[last]);
            b = mod(haah[n - last - 1] - (n - i - 2 < 0 ? 0 : haah[n - i - 2]));
            b = mod(b * inv[n - i - 1]);
            //
            /*a = 0;
            for(int j = last; j < i + 1; j++) {
                a = mod(a + mod((s[j] - 'a') * p[j - last]));
            }
            //
            b = 0;
            for(int j = n - i - 1; j < n - last; j++) {
                b = mod(b + mod((s[j] - 'a') * p[j - (n - i - 1)]));
            }*/
            //
            //cout << last << " " << i << " " << a << "  1\n";
            //cout << n - i - 1 << " " << n - last - 1 << " " << b << "  2\n";
            if(a == b) {
                res += 2;
                last = i + 1;
            } else if(i == n / 2 - 1) {
                res++;
                flag = true;
            }
        }
        if(!flag && n % 2 == 1) res++;
        //
        cout << res << "\n";
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16104 KB Output is correct
2 Correct 17 ms 16104 KB Output is correct
3 Correct 18 ms 15964 KB Output is correct
4 Correct 17 ms 15960 KB Output is correct
5 Correct 17 ms 16112 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16104 KB Output is correct
2 Correct 17 ms 16104 KB Output is correct
3 Correct 18 ms 15964 KB Output is correct
4 Correct 17 ms 15960 KB Output is correct
5 Correct 17 ms 16112 KB Output is correct
6 Correct 18 ms 15964 KB Output is correct
7 Correct 17 ms 16116 KB Output is correct
8 Correct 17 ms 15964 KB Output is correct
9 Correct 18 ms 15964 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16104 KB Output is correct
2 Correct 17 ms 16104 KB Output is correct
3 Correct 18 ms 15964 KB Output is correct
4 Correct 17 ms 15960 KB Output is correct
5 Correct 17 ms 16112 KB Output is correct
6 Correct 18 ms 15964 KB Output is correct
7 Correct 17 ms 16116 KB Output is correct
8 Correct 17 ms 15964 KB Output is correct
9 Correct 18 ms 15964 KB Output is correct
10 Correct 21 ms 16216 KB Output is correct
11 Correct 19 ms 16220 KB Output is correct
12 Correct 21 ms 16220 KB Output is correct
13 Correct 21 ms 16216 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16104 KB Output is correct
2 Correct 17 ms 16104 KB Output is correct
3 Correct 18 ms 15964 KB Output is correct
4 Correct 17 ms 15960 KB Output is correct
5 Correct 17 ms 16112 KB Output is correct
6 Correct 18 ms 15964 KB Output is correct
7 Correct 17 ms 16116 KB Output is correct
8 Correct 17 ms 15964 KB Output is correct
9 Correct 18 ms 15964 KB Output is correct
10 Correct 21 ms 16216 KB Output is correct
11 Correct 19 ms 16220 KB Output is correct
12 Correct 21 ms 16220 KB Output is correct
13 Correct 21 ms 16216 KB Output is correct
14 Correct 349 ms 41956 KB Output is correct
15 Correct 199 ms 36812 KB Output is correct
16 Correct 342 ms 48080 KB Output is correct
17 Correct 198 ms 29956 KB Output is correct