Submission #948754

#	Time	Username	Problem	Language	Result	Execution time	Memory
948754		ifateen	Boarding Passes (BOI22_passes)	C++17	30 / 100	2031 ms	1628 KiB

passes

#include <bits/stdc++.h>
using namespace std;
#define int long long
map<char, int> m;
signed main() {
    string s;
    cin >> s;
    vector<int> v(s.length());
    int cnt = 1;
    for (int i = 0; i < s.length(); ++i) {
        if (m.find(s[i]) != m.end()) v[i] = m[s[i]];
        else v[i] = m[s[i]] = cnt++;
    }
    int G = *max_element(begin(v), end(v));
    if (G == 1) {
        long double n = s.length();
        long double a = floor(n / 2), b = ceil(n / 2);
        cout << fixed << setprecision(8) << (a * (a - 1) + b * (b - 1)) / 4.0;
    } else {
        vector<vector<int>> pos(cnt);
        int n = s.length();
        for (int i = 0; i < n; ++i) pos[v[i]].push_back(i);
        vector<int> order;
        for (int i = 1; i <= G; ++i) order.push_back(i);
        long double ans = 1e18;
        do {
            long double EV = 0;
            set<int> vis;
            for (auto &i: order) {
                for (auto &j: pos[i]) {
                    long double prev = 0, nd = 0;
                    for (int k = 0; k < j; ++k) {
                        if (v[k] == i) prev += 0.5;
                        else if (vis.find(v[k]) != vis.end()) prev += 1;
                        else continue;
                    }
                    for (int k = n - 1; k > j; --k) {
                        if (v[k] == i) nd += 0.5;
                        else if (vis.find(v[k]) != vis.end()) nd += 1;
                        else continue;
                    }
                    EV += min(prev, nd);
                }
                vis.insert(i);
            }
            if (ans > EV) {
                ans = EV;
            }
        } while (next_permutation(begin(order), end(order)));
        cout << fixed << setprecision(8) << ans;
    }
}

Compilation message (stderr)

passes.cpp: In function 'int main()':
passes.cpp:10:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (int i = 0; i < s.length(); ++i) {
      |                     ~~^~~~~~~~~~~~

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