Submission #701967

#	Time	Username	Problem	Language	Result	Execution time	Memory
701967		Johann	Boarding Passes (BOI22_passes)	C++14	100 / 100	467 ms	25284 KiB

passes

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<double> vd;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

vi B;            // bitvector interpretation of the group a person belongs to
vvi mg;          // groupmember
vl dp;           // the results are only 1/2 away from integers, so i store 2 * res in the dp
vvvl pre1, pre2; // pre1[g1][g2][p] = count of passes for the first p people of g1 with people of group g2 (coming from the left)

ll calc(ll k1, ll k2)
{
    return (k1 * (k1 - 1) + k2 * (k2 - 1)) / 2;
}
ll calc(int group, int others, int posInGroup)
{
    ll res = 0;
    for (int g = 0; g < sz(pre1); ++g)
    {
        if (g == group)
        {
            if (posInGroup >= 0)
                res += pre1[group][g][posInGroup];
            if (posInGroup + 1 < sz(pre2[group][g]))
                res += pre2[group][g][posInGroup + 1];
        }
        else if ((1 << g) & others)
        {
            if (posInGroup >= 0)
                res += 2 * pre1[group][g][posInGroup];
            if (posInGroup + 1 < sz(pre2[group][g]))
                res += 2 * pre2[group][g][posInGroup + 1];
        }
    }
    return res;
}
ll compute(int mask, int lg) // lg is the number of the last group
{
    int others = mask ^ (1 << lg);
    ll res = calc(lg, others, -1);
    int l = 0, r = sz(mg[lg]) - 1; // starting with -1 because it is possible, that noone of that group will come from the left side
    int m1, m2;
    while (r - l > 1)
    {
        m1 = (2 * l + r) / 3;
        m2 = (l + 2 * r) / 3;
        assert(m1 != m2);
        ll res1 = calc(lg, others, m1);
        ll res2 = calc(lg, others, m2);
        res = min(res, min(res1, res2));
        if (res1 < res2)
            r = m2 - 1;
        else if (res1 > res2)
            l = m1 + 1;
        else
            l = m1, r = m2;
    }
    for (int i = l; i <= r; ++i)
        res = min(res, calc(lg, others, i));

    return res + dp[others];
}

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
    mg.resize(G);
    for (int i = 0; i < N; ++i)
        mg[P[i] - 'A'].push_back(i);

    // precompute
    pre1.assign(G, vvl(G));
    for (int g1 = 0; g1 < G; ++g1)
    {
        if (sz(mg[g1]) == 0)
            continue;
        for (int g2 = 0; g2 < G; ++g2)
        {
            pre1[g1][g2].resize(sz(mg[g1]));
            int j = 0;
            while (j < sz(mg[g2]) && mg[g2][j] < mg[g1][0])
                ++j;
            pre1[g1][g2][0] = j;
            for (int i = 1; i < sz(pre1[g1][g2]); ++i)
            {
                while (j < sz(mg[g2]) && mg[g2][j] < mg[g1][i])
                    ++j;
                pre1[g1][g2][i] = pre1[g1][g2][i - 1] + j;
            }
        }
    }
    // precompute 2
    for (int g = 0; g < G; ++g)
        reverse(all(mg[g]));
    pre2.assign(G, vvl(G));
    for (int g1 = 0; g1 < G; ++g1)
    {
        if (sz(mg[g1]) == 0)
            continue;
        for (int g2 = 0; g2 < G; ++g2)
        {
            pre2[g1][g2].resize(sz(mg[g1]));
            int j = 0;
            while (j < sz(mg[g2]) && mg[g2][j] > mg[g1][0])
                ++j;
            pre2[g1][g2][0] = j;
            for (int i = 1; i < sz(pre2[g1][g2]); ++i)
            {
                while (j < sz(mg[g2]) && mg[g2][j] > mg[g1][i])
                    ++j;
                pre2[g1][g2][i] = pre2[g1][g2][i - 1] + j;
            }
            reverse(all(pre2[g1][g2]));
        }
    }
    for (int g = 0; g < G; ++g)
        reverse(all(mg[g]));

    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, 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: 40 / 40