oj.uz

Submission #679624

# Submission time Handle Problem Language Result Execution time Memory
679624 2023-01-08T17:14:07 Z zimpha Palinilap (COI16_palinilap) C++17
100 / 100
 190 ms 33688 KB 
#include <iostream>
#include <cassert>
#include <vector>
#include <map>
#include <functional>
#include <algorithm>

using namespace std;

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

int main()
{
    string str;
    cin >> str;
    int len = str.size();

    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:48:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |             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 0 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 212 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1236 KB Output is correct
2 Correct 7 ms 1236 KB Output is correct
3 Correct 8 ms 1260 KB Output is correct
4 Correct 4 ms 1088 KB Output is correct
5 Correct 6 ms 1268 KB Output is correct
6 Correct 7 ms 1448 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 147 ms 17756 KB Output is correct
2 Correct 121 ms 19344 KB Output is correct
3 Correct 105 ms 19352 KB Output is correct
4 Correct 155 ms 23352 KB Output is correct
5 Correct 149 ms 22728 KB Output is correct
6 Correct 157 ms 22672 KB Output is correct
7 Correct 190 ms 23152 KB Output is correct
8 Correct 91 ms 13204 KB Output is correct
9 Correct 143 ms 22612 KB Output is correct
10 Correct 157 ms 22608 KB Output is correct
11 Correct 109 ms 19316 KB Output is correct
12 Correct 156 ms 19504 KB Output is correct
13 Correct 149 ms 18584 KB Output is correct
14 Correct 157 ms 24020 KB Output is correct
15 Correct 158 ms 22980 KB Output is correct
16 Correct 148 ms 25656 KB Output is correct
17 Correct 158 ms 33476 KB Output is correct
18 Correct 134 ms 17412 KB Output is correct
19 Correct 177 ms 33688 KB Output is correct