oj.uz

Submission #982696

# Submission time Handle Problem Language Result Execution time Memory
982696 2024-05-14T16:13:04 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 347 ms 39012 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 17 ms 16100 KB Output is correct
2 Correct 17 ms 15960 KB Output is correct
3 Correct 17 ms 16220 KB Output is correct
4 Correct 17 ms 16104 KB Output is correct
5 Correct 19 ms 15960 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16100 KB Output is correct
2 Correct 17 ms 15960 KB Output is correct
3 Correct 17 ms 16220 KB Output is correct
4 Correct 17 ms 16104 KB Output is correct
5 Correct 19 ms 15960 KB Output is correct
6 Correct 18 ms 16108 KB Output is correct
7 Correct 18 ms 16104 KB Output is correct
8 Correct 17 ms 16108 KB Output is correct
9 Correct 17 ms 15960 KB Output is correct
10 Correct 21 ms 16216 KB Output is correct
11 Correct 20 ms 16604 KB Output is correct
12 Correct 21 ms 16220 KB Output is correct
13 Correct 19 ms 16216 KB Output is correct
14 Correct 347 ms 32840 KB Output is correct
15 Correct 198 ms 32604 KB Output is correct
16 Correct 344 ms 39012 KB Output is correct
17 Correct 212 ms 24820 KB Output is correct