Submission #580190

#	Time	Username	Problem	Language	Result	Execution time	Memory
580190		Josia	Boarding Passes (BOI22_passes)	C++14	25 / 100	2096 ms	3236 KiB

passes

#include <bits/stdc++.h>

using namespace std;

#define int int64_t

signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    string s; cin >> s;

    int n = s.size();

    vector<vector<int>> groupsAlph(26);

    for (int i = 0; i<n; i++) {
        groupsAlph[s[i]-'A'].push_back(i);
    }

    vector<vector<int>> groups;
    for (auto i: groupsAlph) {
        if (i.size()) groups.push_back(i);
    }

    sort(groups.begin(), groups.end());
    double res = 1e18;
    do {
        // for (auto i: groups) {for (int j: i) cerr << j << " "; cerr << "\n";}

        vector<bool> isset(n);
        double blubblubres = 0;                                                 // with this permutation of groups
        for (int i = 0; i<groups.size(); i++) {
            vector<int> pfs = {0};
            for (int j = 0; j<n; j++) pfs.push_back(isset[j] + pfs.back());


            double blubres = 1e18;                                              // find best offset for this group and current situation
            for (int j = 0; j<=groups[i].size(); j++) {
                int n1 = j;
                int n2 = groups[i].size()-j;

                double tmpres = ((n1-1)*n1 + (n2-1)*n2)/4.0;                    // current selected offset

                for (int k = 0; k<n1; k++) {
                    tmpres += pfs[groups[i][k]+1];
                }
                for (int k = n1; k<groups[i].size(); k++) {
                    tmpres += pfs.back() - pfs[groups[i][k]];
                }

                blubres = min(blubres, tmpres);
            }
            blubblubres += blubres;

            for (int j: groups[i]) isset[j] = 1;
        }
        // cerr << blubblubres << "-----------\n\n";
        res = min(res, blubblubres);
    } while (next_permutation(groups.begin(), groups.end()));

    
    cout << setprecision(100) << res << "\n";

    return 0;
}

Compilation message (stderr)

passes.cpp: In function 'int main()':
passes.cpp:33:26: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::vector<long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for (int i = 0; i<groups.size(); i++) {
      |                         ~^~~~~~~~~~~~~~
passes.cpp:39:30: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |             for (int j = 0; j<=groups[i].size(); j++) {
      |                             ~^~~~~~~~~~~~~~~~~~
passes.cpp:48:35: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |                 for (int k = n1; k<groups[i].size(); k++) {
      |                                  ~^~~~~~~~~~~~~~~~~

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