oj.uz

Submission #660425

# Submission time Handle Problem Language Result Execution time Memory
660425 2022-11-21T20:15:31 Z SansPapyrus683 Palinilap (COI16_palinilap) C++17
100 / 100
 161 ms 33628 KB 
#include <iostream>
#include <cassert>
#include <vector>
#include <map>
#include <functional>
#include <algorithm>

using namespace std;

/** sauce: https://usaco.guide/gold/modular */
long long pow_mod(long long x, long long n, long long mod) {
    assert(n >= 0);
    x %= mod;
    long long res = 1;
    while (n > 0) {
        if (n % 2 == 1) {
            res = res * x % mod;
        }
        x = x * x % mod;
        n /= 2;
    }
    return res;
}

class HashedString {
    private:
        static const long long MOD = 1e9 + 9;
        static const long long POW = 101;

        static vector<long long> pow;
        static vector<long long> mod_inv;
        
        const string& s;
        vector<long long> p_hash;
    public:
        HashedString(const string& s) : s(s), p_hash(s.size() + 1) {
            while (pow.size() < s.size()) {
                pow.push_back((pow.back() * POW) % MOD);
                mod_inv.push_back(pow_mod(pow.back(), MOD - 2, MOD));
            }

            p_hash[0] = 0;
            for (int i = 0; i < s.size(); i++) {
                p_hash[i + 1] = (p_hash[i] + s[i] * pow[i] % MOD) % MOD;
            }
        }

        long long hash(int from, int to) {
            long long pref = (p_hash[to + 1] - p_hash[from] + MOD) % MOD;
            return pref * mod_inv[from] % MOD;
        }

        long long hash(int from, int to, const pair<int, char>& rep) {
            long long pref = p_hash[to + 1] - p_hash[from];
            if (from <= rep.first && rep.first <= to) {
                pref += rep.second * pow[rep.first] - s[rep.first] * pow[rep.first];
            }
            return (pref % MOD + MOD) * mod_inv[from] % MOD;
        }
};
vector<long long> HashedString::pow = {1};
vector<long long> HashedString::mod_inv = {1};

int last_true(int lo, int hi, function<bool(int)> check) {
    int valid = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (check(mid)) {
            lo = mid + 1;
            valid = mid;
        } else {
            hi = mid - 1;
        }
    }
    return valid;
}

vector<long long> range_res(int size, const vector<pair<int, int>>& ranges) {
    vector<long long> arr(size + 1);
    for (const auto& [a, b] : ranges) {
        arr[a]++;
        arr[b + 1]--;
    }
    for (int i = 1; i < size; i++) {
        arr[i] += arr[i - 1];
    }
    for (const auto& [a, b] : ranges) {
        arr[b + 1] -= b - a + 1;
    }
    for (int i = 1; i < size; i++) {
        arr[i] += arr[i - 1];
    }
    arr.pop_back();
    return arr;
}

/**
 * https://oj.uz/problem/view/COI16_palinilap
 * baccb should output 9
 * slavko should output 7
 */
int main() {
    string str;
    cin >> str;
    int len = str.size();  // shorthand

    string rev_str = str;
    reverse(rev_str.begin(), rev_str.end());
    HashedString h_str(str), h_rev_str(rev_str);

    auto is_pal = [&](int from, int to) {
        return h_str.hash(from, to)
                == h_rev_str.hash(len - to - 1, len - from - 1);
    };
    auto is_pal_rep = [&](int from, int to, pair<int, char> rep) {
        pair<int, char> r_rep{len - rep.first - 1, rep.second};
        return h_str.hash(from, to, rep)
                == h_rev_str.hash(len - to - 1, len - from - 1, r_rep);
    };

    function<bool(int)> check;
    vector<map<char, long long>> change_inc(len);
    vector<pair<int, int>> removal1, removal2;
    long long init_amt = 0;
    for (int c = 0; c < len; c++) {
        int most = min(c, len - c - 1);
        check = [&](int d) { return is_pal(c - d, c + d); };
        int raw_pal = last_true(0, most, check);
        init_amt += raw_pal + 1;
        if (raw_pal > 0) {
            removal1.push_back({c - raw_pal, c - 1});
            removal2.push_back({c + 1, c + raw_pal});
        }

        pair<int, char> rep = {c + raw_pal + 1, str[c - raw_pal - 1]};
        check = [&](int d) { return is_pal_rep(c - d, c + d, rep); };
        int rep_pal = last_true(raw_pal + 1, most, check);
        if (rep_pal != -1) {
            change_inc[rep.first][rep.second] += rep_pal - raw_pal;
            change_inc[c - raw_pal - 1][str[c + raw_pal + 1]] += rep_pal - raw_pal;
        }

        if (c < len - 1) {
            int most = min(c + 1, len - c - 1);
            check = [&](int d) { return is_pal(c - d + 1, c + d); };
            int raw_pal = last_true(0, most, check);
            init_amt += raw_pal;
            if (raw_pal > 0) {
                removal1.push_back({c - raw_pal + 1, c});
                removal2.push_back({c + 1, c + raw_pal});
            }

            pair<int, char> rep = {c + raw_pal + 1, str[c - raw_pal]};
            check = [&](int d) { return is_pal_rep(c - d + 1, c + d, rep); };
            int rep_pal = last_true(raw_pal + 1, most, check);
            if (rep_pal != -1) {
                change_inc[rep.first][rep.second] += rep_pal - raw_pal;
                change_inc[c - raw_pal][str[c + raw_pal + 1]] += rep_pal - raw_pal;
            }
        }
    }

    for (pair<int, int>& r : removal2) {
        r = {len - r.second - 1, len - r.first - 1};
    }
    vector<long long> bad1 = range_res(len, removal1);
    vector<long long> bad2 = range_res(len, removal2);
    std::reverse(bad2.begin(), bad2.end());
    
    long long max_weight = init_amt;
    for (int i = 0; i < len; i++) {
        long long max_inc = 0;
        for (const auto& [_, i] : change_inc[i]) {
            max_inc = max(max_inc, i);
        }
        max_weight = max(max_weight, init_amt + max_inc - bad1[i] - bad2[i]);
    }

    cout << max_weight << endl;
}

Compilation message

palinilap.cpp: In constructor 'HashedString::HashedString(const string&)':
palinilap.cpp:43:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             for (int i = 0; i < s.size(); i++) {
      |                             ~~^~~~~~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1348 KB Output is correct
2 Correct 5 ms 1328 KB Output is correct
3 Correct 6 ms 1236 KB Output is correct
4 Correct 4 ms 980 KB Output is correct
5 Correct 5 ms 1236 KB Output is correct
6 Correct 7 ms 1364 KB Output is correct
7 Correct 7 ms 1876 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 17816 KB Output is correct
2 Correct 134 ms 19296 KB Output is correct
3 Correct 101 ms 19356 KB Output is correct
4 Correct 145 ms 23312 KB Output is correct
5 Correct 161 ms 22820 KB Output is correct
6 Correct 142 ms 22660 KB Output is correct
7 Correct 141 ms 23196 KB Output is correct
8 Correct 74 ms 13292 KB Output is correct
9 Correct 144 ms 22596 KB Output is correct
10 Correct 144 ms 22576 KB Output is correct
11 Correct 105 ms 19388 KB Output is correct
12 Correct 144 ms 19444 KB Output is correct
13 Correct 157 ms 18564 KB Output is correct
14 Correct 150 ms 23984 KB Output is correct
15 Correct 149 ms 23028 KB Output is correct
16 Correct 135 ms 25552 KB Output is correct
17 Correct 159 ms 33572 KB Output is correct
18 Correct 138 ms 17388 KB Output is correct
19 Correct 161 ms 33628 KB Output is correct