oj.uz

Submission #600793

# Submission time Handle Problem Language Result Execution time Memory
600793 2022-07-21T07:51:08 Z alextodoran Boarding Passes (BOI22_passes) C++17
0 / 100
 2 ms 468 KB 
/**
 ____ ____ ____ ____ ____
||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]]++;
    }
}

double minEV[1 << G_MAX];

void update (double &x, const double &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), INT_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++) {
                    double add = 0;
                    for (int i = 0; i < cntL; i++) {
                        add += (double) i / 2;
                        for (int h = 0; h < G; h++) {
                            if ((mask >> h) & 1) {
                                add += pref[inGroup[g][i]][h];
                            }
                        }
                    }
                    for (int i = cntL; i < (int) inGroup[g].size(); i++) {
                        add += (double) ((int) inGroup[g].size() - 1 - i) / 2;
                        for (int h = 0; h < G; h++) {
                            if ((mask >> h) & 1) {
                                add += suff[inGroup[g][i]][h];
                            }
                        }
                    }
                    update(minEV[mask | (1 << g)], minEV[mask] + add);
                }
            }
        }
    }
    cout << minEV[(1 << G) - 1] << "\n";

    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 40.0

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