oj.uz

Submission #1117015

# Submission time Handle Problem Language Result Execution time Memory
1117015 2024-11-22T18:28:26 Z ortsac Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 2196 ms 28824 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int MOD = 1e9 + 7;

int mult(int a, int b) {
    return ((a * b) % MOD);
}

int sum(int a, int b) {
    return ((a + b) % MOD);
}

int binpow(int a, int b) {
    if (b == 0) return 1;
    int c = binpow(a, b/2);
    if ((b % 2LL) == 1LL) return mult(mult(c, c), a);
    else return mult(c, c);
}

struct Hash {
    vector<int> hashS, modInv;

    void build(string s) {
        int n = s.size();
        hashS.resize(n + 1);
        modInv.resize(n + 1);
        hashS[0] = 0;
        modInv[0] = 1;
        int currM = 1;
        for (int i = 1; i <= n; i++) {
            currM = mult(currM, 31);
            modInv[i] = binpow(currM, MOD - 2);
            hashS[i] = sum(hashS[i - 1], mult(((int)(s[i - 1] - 'a')), currM));
        }
    }

    int calc(int i, int j) {
        return sum(MOD, mult(hashS[j] - hashS[i - 1], modInv[i]));
    }
};

int n;
Hash hs;

bool eq(int i, int j) {
    return (hs.calc(i, j) == hs.calc(n - j + 1, n - i + 1));
}

void solve() {
    string s;
    cin >> s;
    hs.build(s);
    n = s.size();
    int qtd = 0;
    int lst = 0;
    for (int i = 1; i <= (n / 2); i++) {
        if (eq(lst + 1, i)) {
            qtd += 2;
            lst = i;
        }
    }
    if (lst != ((n + 1)/2)) {
        qtd++;
    }
    cout << qtd << "\n";
}

int32_t main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 23 ms 592 KB Output is correct
11 Correct 13 ms 780 KB Output is correct
12 Correct 24 ms 848 KB Output is correct
13 Correct 19 ms 848 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 23 ms 592 KB Output is correct
11 Correct 13 ms 780 KB Output is correct
12 Correct 24 ms 848 KB Output is correct
13 Correct 19 ms 848 KB Output is correct
14 Correct 2196 ms 27816 KB Output is correct
15 Correct 1159 ms 28252 KB Output is correct
16 Correct 2082 ms 28824 KB Output is correct
17 Correct 1133 ms 15120 KB Output is correct