oj.uz

Submission #580187

# Submission time Handle Problem Language Result Execution time Memory
580187 2022-06-20T17:15:49 Z Josia Boarding Passes (BOI22_passes) C++14
0 / 100
 2000 ms 3236 KB 
#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 {
        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;
        }
        res = min(res, blubblubres);
    } while (next_permutation(groups.begin(), groups.end()));

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

    return 0;
}

Compilation message

passes.cpp: In function 'int main()':
passes.cpp:32: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]
   32 |         for (int i = 0; i<groups.size(); i++) {
      |                         ~^~~~~~~~~~~~~~
passes.cpp:38: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]
   38 |             for (int j = 0; j<groups[i].size(); j++) {
      |                             ~^~~~~~~~~~~~~~~~~
passes.cpp:47: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]
   47 |                 for (int k = n1; k<groups[i].size(); k++) {
      |                                  ~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Execution timed out 2060 ms 3236 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 38 ms 304 KB Output is correct
4 Correct 31 ms 300 KB Output is correct
5 Incorrect 101 ms 300 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 38 ms 304 KB Output is correct
4 Correct 31 ms 300 KB Output is correct
5 Incorrect 101 ms 300 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Execution timed out 2060 ms 3236 KB Time limit exceeded
7 Halted 0 ms 0 KB -