oj.uz

Submission #588652

# Submission time Handle Problem Language Result Execution time Memory
588652 2022-07-03T19:16:55 Z bebra Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 354 ms 43204 KB 
#include <bits/stdc++.h>
using namespace std;

#define dbg(x) cerr << #x << ": " << x << endl;


template<long long Base, long long Mod>
struct Hash {
    static const long long BASE = Base;
    static const long long MOD = Mod;

    vector<long long> pref;
    vector<long long> powers;
    int size;

    Hash() {}
    Hash(const string& s) {
        int n = s.size() + 1;
        pref.resize(n);
        powers.assign(n, 1);
        for (int i = 1; i < n; ++i) {
            int c = s[i - 1] - 'a' + 1;
            pref[i] = (pref[i - 1] * BASE + c) % MOD;
            powers[i] = (powers[i - 1] * BASE) % MOD;
        }
    }

    long long substr(int l, int r) const {
        ++l, ++r;
        long long result = (pref[r] - pref[l - 1] * powers[r - l + 1]) % MOD;
        if (result < 0) result += MOD;
        return result;
    }
};

struct DoubleHash {
    using hash_t1 = Hash<310073, 1084719133>;
    using hash_t2 = Hash<513101, 1259117633>;
    hash_t1 h1;
    hash_t2 h2;
    DoubleHash(const string& s) {
        h1 = s;
        h2 = s;
    }
    pair<long long, long long> substr(int l, int r) const {
        return {h1.substr(l, r), h2.substr(l, r)};
    }
};


void solve() {
    string s;
    cin >> s;
    int n = s.size();
    DoubleHash h(s);
    int ans = 0;
    int prev_i = 0;
    int i = 0;
    int prev_j = n - 1;
    int j = n - 1;
    vector<bool> used(n);
    while (i < j) {
        if (h.substr(prev_i, i) == h.substr(j, prev_j)) {
            for (int k = prev_i; k <= i; ++k) {
                used[k] = true;
            }
            for (int k = j; k <= prev_j; ++k) {
                used[k] = true;
            }
            ans += 2;
            ++i;
            prev_i = i;
            --j;
            prev_j = j;
        } else {
            ++i;
            --j;
        }
    }
    for (int k = 0; k < n; ++k) {
        if (!used[k]) {
            ++ans;
            break;
        }
    }
    cout << ans << '\n';
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 272 KB Output is correct
10 Correct 4 ms 732 KB Output is correct
11 Correct 3 ms 644 KB Output is correct
12 Correct 3 ms 728 KB Output is correct
13 Correct 3 ms 732 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 272 KB Output is correct
10 Correct 4 ms 732 KB Output is correct
11 Correct 3 ms 644 KB Output is correct
12 Correct 3 ms 728 KB Output is correct
13 Correct 3 ms 732 KB Output is correct
14 Correct 354 ms 43204 KB Output is correct
15 Correct 195 ms 38076 KB Output is correct
16 Correct 330 ms 41016 KB Output is correct
17 Correct 197 ms 23348 KB Output is correct