oj.uz

Submission #581210

# Submission time Handle Problem Language Result Execution time Memory
581210 2022-06-22T11:35:51 Z Josia Boarding Passes (BOI22_passes) C++14
30 / 100
 2000 ms 8892 KB 
#include <bits/stdc++.h>

using namespace std;

#define int int64_t


vector<vector<int>> groups;
int n, g;


vector<vector<int>> groupPFS;


void generateGroupPFS() {
    for (auto i: groups) {
        vector<int> pfs = {0};

        for (int j = 0; j<n; j++) {
            pfs.push_back(pfs.back() + binary_search(i.begin(), i.end(), j));
        }

        groupPFS.push_back(pfs);
    }
}



vector<vector<vector<int>>> prefixsum;

void init() {
    generateGroupPFS();

    prefixsum.assign(g, vector<vector<int>>(g));

    for (int i = 0; i<g; i++) {
        for (int j = 0; j<g; j++) {
            // if (i == j) continue;
            vector<pair<int, int>> costPerElem;
            for (int k = 0; k<groups[i].size(); k++) {
                int l = groupPFS[j][groups[i][k]] - groupPFS[j][0];
                int r = groupPFS[j][n] - groupPFS[j][groups[i][k]];
                costPerElem.push_back({l, r});
            }

            // for (auto i: costPerElem) {
            //     cerr << i.first << " ";
            // }
            // cerr << "\n";
            // for (auto i: costPerElem) {
            //     cerr << i.second << " ";
            // }
            // cerr << "\n\n";


            vector<pair<int, int>> pfs(groups[i].size()+1, {0, 0});

            for (int k = 1; k<=groups[i].size(); k++) {
                pfs[k].first = pfs[k-1].first + costPerElem[k-1].first;
            }

            reverse(pfs.begin(), pfs.end());
            reverse(costPerElem.begin(), costPerElem.end());
            for (int k = 1; k<=groups[i].size(); k++) {
                pfs[k].second = pfs[k-1].second + costPerElem[k-1].second;
            }
            reverse(costPerElem.begin(), costPerElem.end());
            reverse(pfs.begin(), pfs.end());

            // for (auto i: pfs) {
            //     cerr << i.first << " ";
            // }
            // cerr << "\n";
            // for (auto i: pfs) {
            //     cerr << i.second << " ";
            // }
            // cerr << "\n\n";

            vector<int> costForSplit;

            for (int k = 0; k<=groups[i].size(); k++) {
                costForSplit.push_back(pfs[k].first + pfs[k].second);
            }


            prefixsum[i][j] = costForSplit;
        }
    }

    // for (int i = 0; i<g; i++) {
    //     for (int j = 0; j<g; j++) {
    //         for (int k: prefixsum[i][j]) {
    //             cerr << k << " ";
    //         }
    //         cerr << "\n";
    //     }
    //     cerr << "\n";
    // }
}



struct binarySearch {
    int getCostOneToOne(int from, int to, int pos) {
        return prefixsum[from][to][pos];
    }

    double getSelfintersections(int from, int pos) {
        int n1 = pos;
        int n2 = groups[from].size()-pos;
        return ((n1-1)*n1 + (n2-1)*n2)/4.0;
    }

    double getTotalCost(int from, int bm, int pos) {
        double res = getSelfintersections(from, pos);

        for (int j = 0; j<g; j++) {
            if ((1<<j) & bm) {
                res += getCostOneToOne(from, j, pos);
            }
        }
        return res;
    }


    bool check(int from, int bm, int pos) {
        if (pos + 1 > groups[from].size()) return 0 || check(from, bm, pos-1);
        return getTotalCost(from, bm, pos) < getTotalCost(from, bm, pos+1);
    }


    double bs(int from, int bm) {
        int l = 0; int r = groups[from].size();

        for (int i = l; i<=r; i++) {
            // cerr << getTotalCost(from, bm, i) << " ";
        }

        while (l<r) {
            int m = (l + r) / 2;
            if (check(from, bm, m)) r = m;
            else l = m+1;
        }

        // cerr << " --" << l << "-- ";

        return getTotalCost(from, bm, l);
    }
};



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

    string s; cin >> s;

    n = s.size();

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

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

    for (auto i: groupsAlph) {
        if (i.size()) groups.push_back(i);
    }

    g = groups.size();

    init();

    vector<int> order(g);
    iota(order.begin(), order.end(), 0);


    double res = 1e18;
    do {
        // for (int i: order) cerr << i << " ";
        // cerr << "\n";


        double tmpres = 0;

        int bm = 0;

        for (int i: order) {
            binarySearch bs;
            tmpres += bs.bs(i, bm);

            // cerr << "\n";

            bm += 1<<i;
        }
        // cerr << "\n";


        // cerr << tmpres << "\n";
        res = min(tmpres, res);
    } while (next_permutation(order.begin(), order.end()));

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

    return 0;
}

Compilation message

passes.cpp: In function 'void init()':
passes.cpp:40: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]
   40 |             for (int k = 0; k<groups[i].size(); k++) {
      |                             ~^~~~~~~~~~~~~~~~~
passes.cpp:58: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]
   58 |             for (int k = 1; k<=groups[i].size(); k++) {
      |                             ~^~~~~~~~~~~~~~~~~~
passes.cpp:64: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]
   64 |             for (int k = 1; k<=groups[i].size(); k++) {
      |                             ~^~~~~~~~~~~~~~~~~~
passes.cpp:81: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]
   81 |             for (int k = 0; k<=groups[i].size(); k++) {
      |                             ~^~~~~~~~~~~~~~~~~~
passes.cpp: In member function 'bool binarySearch::check(int64_t, int64_t, int64_t)':
passes.cpp:127:21: 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]
  127 |         if (pos + 1 > groups[from].size()) return 0 || check(from, bm, pos-1);
      |             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 9 ms 6488 KB Output is correct
7 Correct 12 ms 8396 KB Output is correct
8 Correct 16 ms 8892 KB Output is correct
9 Correct 13 ms 8044 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 4 ms 336 KB Output is correct
4 Correct 5 ms 212 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 3 ms 212 KB Output is correct
7 Correct 4 ms 328 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 3 ms 212 KB Output is correct
10 Correct 4 ms 212 KB Output is correct
11 Correct 3 ms 212 KB Output is correct
12 Correct 3 ms 212 KB Output is correct
13 Correct 3 ms 212 KB Output is correct
14 Correct 3 ms 324 KB Output is correct
15 Correct 5 ms 212 KB Output is correct
16 Correct 5 ms 212 KB Output is correct
17 Correct 3 ms 212 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 4 ms 336 KB Output is correct
4 Correct 5 ms 212 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 3 ms 212 KB Output is correct
7 Correct 4 ms 328 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 3 ms 212 KB Output is correct
10 Correct 4 ms 212 KB Output is correct
11 Correct 3 ms 212 KB Output is correct
12 Correct 3 ms 212 KB Output is correct
13 Correct 3 ms 212 KB Output is correct
14 Correct 3 ms 324 KB Output is correct
15 Correct 5 ms 212 KB Output is correct
16 Correct 5 ms 212 KB Output is correct
17 Correct 3 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 5 ms 212 KB Output is correct
21 Correct 4 ms 212 KB Output is correct
22 Correct 3 ms 212 KB Output is correct
23 Correct 2 ms 212 KB Output is correct
24 Correct 4 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 3 ms 212 KB Output is correct
27 Correct 3 ms 212 KB Output is correct
28 Correct 3 ms 324 KB Output is correct
29 Correct 3 ms 212 KB Output is correct
30 Correct 3 ms 324 KB Output is correct
31 Correct 3 ms 212 KB Output is correct
32 Correct 3 ms 324 KB Output is correct
33 Correct 4 ms 212 KB Output is correct
34 Correct 4 ms 212 KB Output is correct
35 Correct 2 ms 1028 KB Output is correct
36 Correct 2 ms 1028 KB Output is correct
37 Execution timed out 2082 ms 2144 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 9 ms 6488 KB Output is correct
7 Correct 12 ms 8396 KB Output is correct
8 Correct 16 ms 8892 KB Output is correct
9 Correct 13 ms 8044 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 4 ms 336 KB Output is correct
13 Correct 5 ms 212 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 3 ms 212 KB Output is correct
16 Correct 4 ms 328 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 3 ms 212 KB Output is correct
19 Correct 4 ms 212 KB Output is correct
20 Correct 3 ms 212 KB Output is correct
21 Correct 3 ms 212 KB Output is correct
22 Correct 3 ms 212 KB Output is correct
23 Correct 3 ms 324 KB Output is correct
24 Correct 5 ms 212 KB Output is correct
25 Correct 5 ms 212 KB Output is correct
26 Correct 3 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 5 ms 212 KB Output is correct
30 Correct 4 ms 212 KB Output is correct
31 Correct 3 ms 212 KB Output is correct
32 Correct 2 ms 212 KB Output is correct
33 Correct 4 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 3 ms 212 KB Output is correct
36 Correct 3 ms 212 KB Output is correct
37 Correct 3 ms 324 KB Output is correct
38 Correct 3 ms 212 KB Output is correct
39 Correct 3 ms 324 KB Output is correct
40 Correct 3 ms 212 KB Output is correct
41 Correct 3 ms 324 KB Output is correct
42 Correct 4 ms 212 KB Output is correct
43 Correct 4 ms 212 KB Output is correct
44 Correct 2 ms 1028 KB Output is correct
45 Correct 2 ms 1028 KB Output is correct
46 Execution timed out 2082 ms 2144 KB Time limit exceeded
47 Halted 0 ms 0 KB -