Submission #600846

#	Time	Username	Problem	Language	Result	Execution time	Memory
600846		alextodoran	Boarding Passes (BOI22_passes)	C++17	60 / 100	2058 ms	2528 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];

mt19937 rnd(0);
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);
    }
}

int pref[N_MAX], suff[N_MAX];

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 i = 0; i < N; i++) {
            pref[i] = (i > 0 ? pref[i - 1] : 0) + ((mask >> group[i]) & 1);
        }
        for (int i = N - 1; i >= 0; i--) {
            suff[i] = (i < N - 1 ? suff[i + 1] : 0) + ((mask >> group[i]) & 1);
        }
        for (int g = 0; g < G; g++) {
            if (((mask >> g) & 1) == 0) {
                ll add = 0;
                for (int i = 0; i < (int) inGroup[g].size(); i++) {
                    add += 2 * suff[inGroup[g][i]];
                }
                for (int cntL = 0; cntL <= (int) inGroup[g].size(); cntL++) {
                    int cntR = (int) inGroup[g].size() - cntL;
                    update(minEV[mask | (1 << g)], minEV[mask]
                        + (add + (ll) cntL * (cntL - 1) / 2 + (ll) cntR * (cntR - 1) / 2));
                    if (cntL < inGroup[g].size()) {
                        add -= 2 * suff[inGroup[g][cntL]];
                        add += 2 * pref[inGroup[g][cntL]];
                    }
                }
            }
        }
    }
    ll answer = minEV[(1 << G) - 1];
    if (answer % 2 == 0) {
        cout << answer / 2 << "\n";
    } else {
        cout << answer / 2 << ".5\n";
    }

    return 0;
}

Compilation message (stderr)

passes.cpp: In function 'int main()':
passes.cpp:87:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |                     if (cntL < inGroup[g].size()) {
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~

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