Submission #1098933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098933		not_amir	Boarding Passes (BOI22_passes)	C++14	30 / 100	9 ms	1372 KiB

passes

#include <bits/stdc++.h>
using namespace std;

typedef long double ld;
typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string S;
    cin >> S;
    long long n = S.size();
    bool h[7];
    for(char c : S) {
        h[c- 'A'] = 1;
    }
    vector<char> v;
    for(int i = 0; i < 7; i++)
        if(h[i])
            v.push_back('A' + i);
    ll res = n * n;
    do {
        ll tot = 0;
        vector<bool> on(n);
        vector<ll> rem(n);
        for(int j = 0; j < v.size(); j++) {
            ll ans = 0;
            for(int i = 0, it = 0, sum = 0; i < n; i++) {
                if(S[i] == v[j]) {
                    rem[i] = it++ + 2 * sum;
                    ans += rem[i];
                }
                else if(on[i])
                    sum++;
            }
            ll mini = ans;
            for(int i = n - 1, it = 0, sum = 0; i>= 0; i--) {
                if(S[i] == v[j]) {
                    ans -= rem[i];
                    ans += it++ + 2 * sum;
                    on[i] = 1;
                }
                else if(on[i])
                    sum++;
                mini = min(mini, ans);
            }
            tot += mini;
        }
        res = min(res, tot);
    } while(next_permutation(v.begin(), v.end()));
    cout << fixed << setprecision(6) << ld(res) / 2.0;
}

Compilation message (stderr)

passes.cpp: In function 'int main()':
passes.cpp:26:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for(int j = 0; j < v.size(); j++) {
      |                        ~~^~~~~~~~~~

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