oj.uz

Submission #1089877

# Submission time Handle Problem Language Result Execution time Memory
1089877 2024-09-17T10:51:16 Z alexdumitru Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 120 ms 26816 KB 
#include <iostream>
#include <vector>

std::string s;
int n;

namespace Hash {
    std::vector<long long> sp;
    std::vector<long long> pBase;
    const int MOD = 1e9 + 7;
    const int BASE = 29;

    void init() {
        sp.resize(n + 1);
        pBase.resize(n + 1);
        sp[0] = 0;
        pBase[0] = 1;
        for (int i = 1; i <= n; i++) {
            pBase[i] = pBase[i - 1] * BASE % MOD;
            sp[i] = (sp[i - 1] * BASE + s[i - 1] - 'a') % MOD;
        }
    }

    int get_hash(int l, int r) {
        return ((sp[r + 1] - sp[l] * pBase[r - l + 1]) % MOD + MOD) % MOD;
    }
}

void read() {
    std::cin >> s;
    n = s.length();
}

void solve() {
    int l = 0, r = n - 1;
    int ans = 0;

    while (l <= r) {
        ans++;
        int sz = r - l + 1;
        int lim = sz >> 1;
        int lgmin = sz;
        for (int lg = 1; lg <= lim; lg++) {
            if (Hash::get_hash(l, l + lg - 1) == Hash::get_hash(r - lg + 1, r)) {
                lgmin = lg;
                ans++;
                break;
            }
        }
        l += lgmin;
        r -= lgmin;
    }

    std::cout << ans << '\n';
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    std::cin >> t;
    while (t--) {
        read();
        Hash::init();
        solve();
    }

    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 672 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 2 ms 604 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 672 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 120 ms 26816 KB Output is correct
15 Correct 74 ms 26344 KB Output is correct
16 Correct 118 ms 26264 KB Output is correct
17 Correct 60 ms 14312 KB Output is correct