Submission #600801

#	Time	Username	Problem	Language	Result	Execution time	Memory
600801		alextodoran	Boarding Passes (BOI22_passes)	C++17	0 / 100	1 ms	340 KiB

passes

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100000;
const int G_MAX = 15;

int G, N;
int group[N_MAX];
vector <int> inGroup[G_MAX];
int pref[N_MAX][G_MAX];
int suff[N_MAX][G_MAX];

void input () {
    string S;
    cin >> S;
    N = (int) S.size();
    bool occ[26];
    fill(occ, occ + 26, false);
    for (int i = 0; i < N; i++) {
        group[i] = (int) (S[i] - 'A');
        occ[group[i]] = true;
    }
    int id[26];
    for (int g = 0; g < 26; g++) {
        if (occ[g] == true) {
            id[g] = G++;
        }
    }
    for (int i = 0; i < N; i++) {
        group[i] = id[group[i]];
        inGroup[group[i]].push_back(i);
    }
    pref[0][group[0]] = 1;
    for (int i = 1; i < N; i++) {
        for (int g = 0; g < G; g++) {
            pref[i][g] = pref[i - 1][g];
        }
        pref[i][group[i]]++;
    }
    suff[N - 1][group[N - 1]] = 1;
    for (int i = N - 2; i >= 0; i--) {
        for (int g = 0; g < G; g++) {
            suff[i][g] = suff[i + 1][g];
        }
        suff[i][group[i]]++;
    }
}

ll minEV[1 << G_MAX];

void update (ll &x, const ll &y) {
    if (y < x) {
        x = y;
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(4);

    input();
//    cout << N << " " << G << "\n";
//    for (int i = 0; i < N; i++) {
//        cout << group[i] << " ";
//    }
//    cout << "\n";

    fill(minEV, minEV + (1 << G), LLONG_MAX);
    minEV[0] = 0;
    for (int mask = 0; mask < (1 << G) - 1; mask++) {
        for (int g = 0; g < G; g++) {
            if (((mask >> g) & 1) == 0) {
                for (int cntL = 0; cntL <= (int) inGroup[g].size(); cntL++) {
                    ll add = 0;
                    for (int i = 0; i < cntL; i++) {
                        add += i;
                        for (int h = 0; h < G; h++) {
                            if ((mask >> h) & 1) {
                                add += 2 * pref[inGroup[g][i]][h];
                            }
                        }
                    }
                    for (int i = cntL; i < (int) inGroup[g].size(); i++) {
                        add += ((int) inGroup[g].size() - 1 - i);
                        for (int h = 0; h < G; h++) {
                            if ((mask >> h) & 1) {
                                add += 2 * suff[inGroup[g][i]][h];
                            }
                        }
                    }
                    update(minEV[mask | (1 << g)], minEV[mask] + add);
                }
            }
        }
    }
    cout << (long double) minEV[(1 << G) - 1] / 2 << "\n";

    return 0;
}

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