Submission #701900

#	Time	Username	Problem	Language	Result	Execution time	Memory
701900		Johann	Boarding Passes (BOI22_passes)	C++14	60 / 100	2077 ms	1108 KiB

passes

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
#define sz(x) (int)(x).size()

vi B;
vl dp; // the results are only 1/2 away from integers, so i store 2 * res in the dp

ll calc(ll k1, ll k2)
{
    return (k1 * (k1 - 1) + k2 * (k2 - 1)) / 2;
}
double expectOneGroup(ll N)
{
    ll k1 = ceil(N / (double)2), k2 = floor(N / (double)2);
    return calc(k1, k2) / (double)2;
}
ll compute(int mask, int lg) // lg is a bitvector with the bit of the group set
{
    int others = mask ^ lg;
    ll k1 = 0, k2 = 0; // passenger split of this Gruop lg
    ll o1 = 0, o2 = 0; // other passengers l and right
    ll safeOtherCost = 0;

    for (int i = sz(B) - 1; i >= 0; --i)
        if (B[i] == lg)
            ++k2, safeOtherCost += 2 * o2;
        else if (B[i] & mask)
            ++o2;

    ll res = dp[others] + safeOtherCost + calc(k1, k2);
    for (int i = 0; i < sz(B); ++i)
    {
        if (B[i] == lg)
        {
            ++k1, --k2;
            safeOtherCost = safeOtherCost - 2 * o2 + 2 * o1;
        }
        else if (B[i] & mask)
        {
            ++o1, --o2;
        }
        res = min(res, dp[others] + safeOtherCost + calc(k1, k2));
    }
    return res;
}

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

    string P;
    cin >> P;
    ll N = sz(P);
    int G = 0;
    B.resize(N);
    for (int i = 0; i < N; ++i)
        B[i] = (1 << (P[i] - 'A')), G = max(G, P[i] - 'A');
    ++G; // to get the size
    dp.assign(1 << G, calc(100100, 100100));
    dp[0] = 0;
    for (int i = 1; i < sz(dp); ++i)
    {
        for (int j = 0; j < G; ++j)
        { // last group to enter
            if (((1 << j) & i) == 0)
                continue;
            dp[i] = min(dp[i], compute(i, (1 << j)));
        }
    }
    // double res = expectOneGroup(N);
    printf("%f\n", dp[(1 << G) - 1] / (double)2);
    return 0;
}

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