제출 #601139

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
601139		alextodoran	Boarding Passes (BOI22_passes)	C++17	60 / 100	215 ms	37756 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;
//    for (int i = 0; i < 100000; i++) {
//        S += (char) (rnd() % 15 + 'A');
//    }
    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 L[N_MAX], R[N_MAX];
int pref[N_MAX][G_MAX], suff[N_MAX][G_MAX];
ll prefSum[N_MAX][G_MAX], suffSum[N_MAX][G_MAX];

void precalc () {
    for (int i = 0; i < N; i++) {
        if (i > 0) {
            for (int g = 0; g < G; g++) {
                pref[i][g] = pref[i - 1][g];
            }
        }
        pref[i][group[i]]++;
    }
    for (int i = N - 1; i >= 0; i--) {
        if (i < N - 1) {
            for (int g = 0; g < G; g++) {
                suff[i][g] = suff[i + 1][g];
            }
        }
        suff[i][group[i]]++;
    }
    int last[G_MAX];
    fill(last, last + G, -1);
    for (int i = 0; i < N; i++) {
        L[i] = last[group[i]];
        last[group[i]] = i;
        if (L[i] != -1) {
            for (int g = 0; g < G; g++) {
                prefSum[i][g] = prefSum[L[i]][g];
            }
        }
        for (int g = 0; g < G; g++) {
            prefSum[i][g] += pref[i][g];
        }
    }
    fill(last, last + G, -1);
    for (int i = N - 1; i >= 0; i--) {
        R[i] = last[group[i]];
        last[group[i]] = i;
        if (R[i] != -1) {
            for (int g = 0; g < G; g++) {
                suffSum[i][g] += suffSum[R[i]][g];
            }
        }
        for (int g = 0; g < G; g++) {
            suffSum[i][g] += suff[i][g];
        }
    }
}

ll f (int mask, int g, int k) {
    ll ret;
    if (k == 0) {
        int i = inGroup[g][0];
        int gr = suff[i][g];
        ret = (ll) gr * (gr - 1) / 2;
        while (mask > 0) {
            int h = __builtin_ctz(mask & -mask);
            mask ^= (1 << h);
            ret += 2 * suffSum[i][h];
        }
    } else {
        int i = inGroup[g][k - 1];
        int gl = pref[i][g], gr = suff[R[i]][g];
        ret = (ll) gl * (gl - 1) / 2 + (ll) gr * (gr - 1) / 2;
        while (mask > 0) {
            int h = __builtin_ctz(mask & -mask);
            mask ^= (1 << h);
            ret += 2 * prefSum[i][h] + 2 * suffSum[R[i]][h];
        }
    }
    return ret;
}

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();
    precalc();
    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) {
                int l = 0, r = (int) inGroup[g].size();
                while (l < r) {
                    int mid = (l + r) / 2;
                    if (f(mask, g, mid) <= f(mask, g, mid + 1)) {
                        r = mid;
                    } else {
                        l = mid + 1;
                    }
                }
                update(minEV[mask ^ (1 << g)], minEV[mask] + f(mask, g, l));
            }
        }
    }
    ll answer = minEV[(1 << G) - 1];
    if (answer % 2 == 0) {
        cout << answer / 2 << "\n";
    } else {
        cout << answer / 2 << ".5\n";
    }

    return 0;
}

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