Submission #583494

#	Time	Username	Problem	Language	Result	Execution time	Memory
583494		Cyanmond	Boarding Passes (BOI22_passes)	C++17	100 / 100	587 ms	377436 KiB

passes

#include <algorithm>
#include <cassert>
#include <iostream>
#include <limits>
#include <string>
#include <vector>

using namespace std;

using i64 = long long int;
constexpr i64 inf64 = numeric_limits<i64>::max() / 3;

#define ALL(x) (x).begin(), (x).end()
#define REP_3(i, l, r) for (int i = (l); i < (r); ++i)
#define RVP_3(i, l, r) for (int i = (r - 1); i >= (l); --i)
#define REP(i, N) REP_3(i, 0, N)
#define RVP(i, N) RVP_3(i, 0, N)

void answer(const i64 x) {
    cout << x / 2;
    if (x % 2 == 1) cout << ".5" << endl;
}

template <typename T> void chmin(T &a, const T b) {
    if (a > b) a = b;
}

int main() {
    string s;
    cin >> s;
    vector<int> S;
    for (const int e : s) S.push_back(e - 'A');
    const int N = (int)S.size();
    const int G = *max_element(ALL(S)) + 1;

    vector<vector<int>> g_list(G);
    REP(i, N) g_list[S[i]].push_back(i);

    vector<vector<i64>> l_v(G, vector<i64>(N + 1));
    auto r_v = l_v;
    vector l_v_w(G, vector(G, vector(N + 1, (i64)0)));
    auto r_v_w = l_v_w;

    REP(i, N) {
        ++l_v[S[i]][i + 1];
        ++r_v[S[i]][i];
        REP(x, G) {
            const int p1 = (int)(upper_bound(ALL(g_list[x]), i) - g_list[x].begin()) - 1;
            const int p2 = (int)(lower_bound(ALL(g_list[x]), i) - g_list[x].begin());
            l_v_w[S[i]][x][i + 1] += (int)g_list[x].size() - p1;
            r_v_w[S[i]][x][i] += p2;
        }
    }
    REP(x, G) {
        REP(i, N) l_v[x][i + 1] += l_v[x][i];
        RVP(i, N) r_v[x][i] += r_v[x][i + 1];
        REP(y, G) {
            REP(i, N) l_v_w[x][y][i + 1] += l_v_w[x][y][i];
            RVP(i, N) r_v_w[x][y][i] += r_v_w[x][y][i + 1];
        }
    }

    auto calc_bound = [&](const int s, const int x) {
        i64 all_sum = 0;
        REP(i, G) {
            if (s & (1 << i)) all_sum += l_v[i][g_list[x].back()] * 2;
            if (i == x) all_sum += l_v[i][g_list[x].back()];
        }
        int ok = -1, ng = (int)g_list[x].size();
        while (ng - ok > 1) {
            const int m = (ok + ng) / 2;
            const int p = g_list[x][m];
            i64 l_sum = 0, r_sum = 0;
            REP(i, G) {
                const i64 l = l_v[i][p + 1], r = r_v[i][p];
                if (s & (1 << i)) {
                    l_sum += l * 2;
                    r_sum += r * 2;
                }
                if (i == x) {
                    l_sum += l;
                    r_sum += r;
                }
            }
            (l_sum <= r_sum ? ok : ng) = m;
        }
        return ok;
        // time complexity O(G log N)
    };

    auto calc_cost = [&](const int s, const int x, const int m) {
        i64 ret = 0;
        const int z = (int)g_list[x].size();
        if (m != -1) {
            const int p = g_list[x][m];
            REP(i, G) {
                if (s & (1 << i)) ret += (l_v_w[i][x][p] - l_v[i][p] * (z - m)) * 2;
                if (i == x) ret += l_v_w[i][x][p] - l_v[i][p] * (z - m);
            }
        }
        if (m != z - 1) {
            const int p = g_list[x][m + 1];
            REP(i, G) {
                if (s & (1 << i)) ret += (r_v_w[i][x][p + 1] - r_v[i][p + 1] * (m + 1)) * 2;
                if (i == x) ret += r_v_w[i][x][p + 1] - r_v[i][p + 1] * (m + 1);
            }
        }
        return ret;
    };

    vector<i64> dp(1 << G, inf64);
    dp[0] = 0;

    REP(bit, 1 << G) {
        REP(x, G) {
            if (g_list[x].empty()) {
                chmin(dp[bit | (1 << x)], dp[bit]);
                continue;
            }
            if (bit & (1 << x)) continue;
            const int m = calc_bound(bit, x);
            const i64 cost = calc_cost(bit, x, m);
            chmin(dp[bit | (1 << x)], dp[bit] + cost);
        }
    }
    answer(dp[(1 << G) - 1]);
}

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