oj.uz

Submission #599828

# Submission time Handle Problem Language Result Execution time Memory
599828 2022-07-20T01:31:17 Z yanndev Boarding Passes (BOI22_passes) C++17
0 / 100
 0 ms 212 KB 
#include <bits/stdc++.h>
#define int long long
#define lgd long long
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 = 4 * esp + ((int)vals[lst].size() * ((int)vals[lst].size() - 1));
                
                // 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, 4 * esp + (((id) * (id - 1)) + ((int)vals[lst].size() - id) * ((int)vals[lst].size() - (id + 1))));
                }

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -