Submission #581240

#	Time	Username	Problem	Language	Result	Execution time	Memory
581240		Josia	Boarding Passes (BOI22_passes)	C++14	100 / 100	274 ms	30968 KiB

passes

#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);




    vector<double> dp(1<<g, 1e18);
    dp[0] = 0;

    for (int i = 1; i<1<<g; i++) {
        for (int j = 0; j<g; j++) {
            if (1<<j & i) {
                binarySearch bs;
                dp[i] = min(dp[i], bs.bs(j, i^(1<<j)) + dp[i^(1<<j)]);
            }
        }
    }

    cout << setprecision(100) << dp[(1<<g)-1] << "\n";






    // 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 (stderr)

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 / 5
• Subtask 2: 25 / 25
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40