oj.uz

Submission #660322

# Submission time Handle Problem Language Result Execution time Memory
660322 2022-11-21T15:34:47 Z SansPapyrus683 Palinilap (COI16_palinilap) C++17
100 / 100
 152 ms 33656 KB 
#include <iostream>
#include <cassert>
#include <vector>
#include <map>
#include <functional>
#include <algorithm>

// #include "debugging.hpp"

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];
            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;
        }
        // printf("%i: %i %i\n", c, raw_pal, rep_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;
            }
            // printf("%i %i: %i %i\n", c, c + 1, raw_pal, rep_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:45:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             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 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 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 5 ms 1324 KB Output is correct
2 Correct 5 ms 1236 KB Output is correct
3 Correct 6 ms 1236 KB Output is correct
4 Correct 5 ms 1016 KB Output is correct
5 Correct 6 ms 1236 KB Output is correct
6 Correct 7 ms 1460 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 141 ms 17720 KB Output is correct
2 Correct 104 ms 19400 KB Output is correct
3 Correct 103 ms 19496 KB Output is correct
4 Correct 144 ms 23240 KB Output is correct
5 Correct 142 ms 22744 KB Output is correct
6 Correct 142 ms 22700 KB Output is correct
7 Correct 139 ms 23092 KB Output is correct
8 Correct 73 ms 13212 KB Output is correct
9 Correct 143 ms 22636 KB Output is correct
10 Correct 139 ms 22584 KB Output is correct
11 Correct 93 ms 19312 KB Output is correct
12 Correct 137 ms 19456 KB Output is correct
13 Correct 143 ms 18504 KB Output is correct
14 Correct 141 ms 24068 KB Output is correct
15 Correct 139 ms 23024 KB Output is correct
16 Correct 129 ms 25608 KB Output is correct
17 Correct 152 ms 33548 KB Output is correct
18 Correct 126 ms 17424 KB Output is correct
19 Correct 152 ms 33656 KB Output is correct