제출 #694967

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
694967		finn__	Boarding Passes (BOI22_passes)	C++17	100 / 100	384 ms	19012 KiB

passes

#include <bits/stdc++.h>
using namespace std;

template <typename T>
struct PrefixSum
{
    vector<T> t;

    PrefixSum() {}

    PrefixSum(vector<T> const &v)
    {
        t = vector<T>(v.begin(), v.end());
        for (size_t i = 1; i < t.size(); i++)
            t[i] += t[i - 1];
    }

    T range_sum(size_t i, size_t j)
    {
        return t[j] - (i ? t[i - 1] : 0);
    }
};

vector<PrefixSum<unsigned>> group_sum;

unsigned sum_groups(size_t i, size_t j, unsigned mask)
{
    unsigned x = 0;
    for (unsigned k = 0; k < group_sum.size(); k++)
        if (mask & (1 << k))
            x += group_sum[k].range_sum(i, j);
    return x;
}

vector<vector<vector<unsigned>>> num_smaller_members, num_greater_members;

uint64_t sum_smaller_members(unsigned curr_group, unsigned k, unsigned mask)
{
    if (k == num_greater_members[curr_group][0].size())
        return 0;
    uint64_t x = 0;
    for (unsigned j = 0; j < num_smaller_members.size(); j++)
        if (mask & (1 << j))
            x += num_smaller_members[curr_group][j][k];
    return x;
}

uint64_t sum_greater_members(unsigned curr_group, unsigned k, unsigned mask)
{
    if (k == num_greater_members[curr_group][0].size())
        return 0;
    uint64_t x = 0;
    for (unsigned j = 0; j < num_greater_members.size(); j++)
        if (mask & (1 << j))
            x += num_greater_members[curr_group][j][k];
    return x;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    string s;
    cin >> s;
    size_t n = s.size(), g = 1;
    for (char const &c : s)
        g = max<size_t>(g, c - 'A' + 1);

    vector<vector<unsigned>> groups(g);
    for (unsigned i = 0; i < n; i++)
        groups[s[i] - 'A'].push_back(i);

    group_sum = vector<PrefixSum<unsigned>>(g);
    for (unsigned i = 0; i < g; i++)
    {
        vector<unsigned> z(s.size(), 0);
        for (unsigned const &j : groups[i])
            z[j] = 1;
        group_sum[i] = PrefixSum(z);
    }

    // For each member of a group, the prefix / suffix sum of the number of
    // smaller / greater elements of the groups members
    num_smaller_members = vector<vector<vector<unsigned>>>(g, vector<vector<unsigned>>(g)),
    num_greater_members = vector<vector<vector<unsigned>>>(g, vector<vector<unsigned>>(g));

    for (size_t i = 0; i < g; i++)
    {
        for (size_t j = 0; j < g; j++)
        {
            num_smaller_members[i][j] = vector<unsigned>(groups[i].size());
            for (size_t k = 0; k < groups[i].size(); k++)
                num_smaller_members[i][j][k] = group_sum[j].range_sum(0, groups[i][k]);

            num_greater_members[i][j] = vector<unsigned>(groups[i].size());
            for (size_t k = 0; k < groups[i].size(); k++)
                num_greater_members[i][j][k] = group_sum[j].range_sum(groups[i][k], n - 1);

            for (size_t k = 1; k < groups[i].size(); k++)
                num_smaller_members[i][j][k] += num_smaller_members[i][j][k - 1];
            for (size_t k = groups[i].size() - 2; k < groups[i].size(); k--)
                num_greater_members[i][j][k] += num_greater_members[i][j][k + 1];
        }
    }

    vector<uint64_t> dp(1 << g, UINT64_MAX);
    dp[0] = 0;

    for (unsigned mask = 0; mask < 1U << g; mask++)
    {
        for (unsigned i = 0; i < g; i++)
            if (mask & (1 << i)) // Let i be the last group borded.
            {
                // Binary search over the members of i for the point where it
                // is better to board from the back than from the front.
                size_t a = 0, b = groups[i].size();
                while (a < b)
                {
                    size_t mid = (a + b) / 2;
                    unsigned front_cost =
                        sum_groups(0, groups[i][mid], mask ^ (1 << i)) * 2 +
                        sum_groups(0, groups[i][mid], 1 << i) - 1;
                    unsigned back_cost =
                        sum_groups(groups[i][mid], n - 1, mask ^ (1 << i)) * 2 +
                        sum_groups(groups[i][mid], n - 1, 1 << i) - 1;

                    if (front_cost < back_cost)
                        a = mid + 1;
                    else
                        b = mid;
                }

                // a is the first to board backwards.
                dp[mask] = min<uint64_t>(dp[mask], dp[mask ^ (1 << i)] +
                                                       ((a ? sum_smaller_members(i, a - 1, mask ^ (1 << i)) : 0) +
                                                        sum_greater_members(i, a, mask ^ (1 << i))) *
                                                           2 +
                                                       ((a > 1) ? sum_smaller_members(i, a - 2, 1 << i) : 0) +
                                                       ((a + 1 < groups[i].size()) ? sum_greater_members(i, a + 1, 1 << i) : 0));
            }
    }

    cout << setprecision(7) << fixed << (long double)dp.back() / 2.0 << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 25 / 25
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40