Submission #599830

#	Time	Username	Problem	Language	Result	Execution time	Memory
599830		yanndev	Boarding Passes (BOI22_passes)	C++17	60 / 100	2091 ms	2612 KiB

passes

#include <bits/stdc++.h>
#define int long long
#define lgd long double
using namespace std;

lgd dp[(int)(1 << 15) + 42];
vector<int> vals[16];

signed main() {
    string s;
    cin >> s;
    int n = (int)s.size();
    /*for (int i = 0; i < n; i++)
        s += 'A';*/
    int g = 0;
    vector<char> comp {};

    for (int i = 0; i < n; i++)
        comp.push_back(s[i]);

    sort(comp.begin(), comp.end());
    comp.resize(unique(comp.begin(), comp.end()) - comp.begin());

    for (int i = 0; i < n; i++)
        vals[lower_bound(comp.begin(), comp.end(), s[i]) - comp.begin()].push_back(i);

    g = (int)comp.size();
    //cout << g << '\n';
    dp[0] = 0;

    for (int mask = 1; mask < (1 << g); mask++) {
        dp[mask] = 1e18;

        vector<int> pref (n, 0);
        for (int group = 0; group < g; group++)
            if (mask & (1 << group))
                for (auto& x: vals[group])
                    pref[x]++;
        for (int pos = 1; pos < n; pos++)
            pref[pos] += pref[pos - 1];

        for (int lst = 0; lst < g; lst++) {
            if (mask & (1 << lst)) {
                // put everyone to the left 
                lgd esp = 0;
                for (int id = 0; id < (int)vals[lst].size(); id++) {
                    // inversions bcs of other groups, remove the ones from lst
                    esp += pref[vals[lst][id]] - (id + 1);
                }
                // add expected inversions from lst permutations
                lgd transi = esp + ((int)vals[lst].size() * ((int)vals[lst].size() - 1)) / 4.;
                
                // fix right limit
                for (int id = (int)vals[lst].size() - 1; id >= 0; id--) {
                    // remove from the left side
                    esp -= pref[vals[lst][id]];
                    esp += (id + 1);

                    // inversions bcs of other groups
                    esp += pref.back() - pref[vals[lst][id]];
                    // remove from lst
                    esp -= (int)vals[lst].size() - (id + 1);
                    transi = min(transi, esp + (((id) * (id - 1)) + ((int)vals[lst].size() - id) * ((int)vals[lst].size() - (id + 1))) / 4.);
                }

                dp[mask] = min(dp[mask], dp[mask ^ (1 << lst)] + transi);
            }
        }
    }
    
    cout << setprecision(42) << dp[(1 << g) - 1] << '\n';
}

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