Submission #660188

#	Time	Username	Problem	Language	Result	Execution time	Memory
660188		SansPapyrus683	Palinilap (COI16_palinilap)	C++17	0 / 100	135 ms	14596 KiB

palinilap

#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 = 5;

        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) {
        // cout << lo << ' ' << hi << endl;
        int mid = (lo + hi) / 2;
        if (check(mid)) {
            lo = mid + 1;
            valid = mid;
        } else {
            hi = mid - 1;
        }
    }
    return valid;
}

/**
 * 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);
    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;

        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;

            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);
        }
    }

    long long max_inc = 0;
    for (const map<char, long long>& c : change_inc) {
        for (const auto& [_, i] : c) {
            max_inc = max(max_inc, i);
        }
    }

    cout << init_amt + max_inc << endl;
}

Compilation message (stderr)

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: 0 / 17
• Subtask 2: 0 / 37
• Subtask 3: 0 / 46