Submission #722924

#	Time	Username	Problem	Language	Result	Execution time	Memory
722924		dxz05	Boarding Passes (BOI22_passes)	C++17	30 / 100	2051 ms	1936 KiB

passes

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define all(x) (x).begin(), (x).end()
#define MP make_pair
const int N = 100500;

long double exp_inv(ll n){
    return (long double) n * (n - 1); // should be divided by 4
}

vector<int> pos[140];

void solve(){
    string s;
    cin >> s;
    int n = (int)s.size();

    string alphabet;
    for (int i = 0; i < n; i++){
        if (pos[s[i]].empty()) alphabet += s[i];
        pos[s[i]].push_back(i);
    }

    sort(all(alphabet));

    int m1 = (n - 1) / 2;
    int m2 = m1 + 1;

    long double ans = 5e18;

    do {
        long double tot = 0;
        vector<bool> used(n, false);
        vector<int> cnt(n, 0);

        for (char c : alphabet){
            ll sum_l = 0;
            vector<int> diff;

            int sz = (int) pos[c].size();

            for (int i : pos[c]){
                int l = cnt[i];
                int r = cnt.back() - cnt[i];
                sum_l += l;
                diff.push_back(r - l);
            }

            sort(all(diff));

            long double cur = 5e18;
            for (int half = 0; half <= sz; half++){
                if (half > 0) sum_l += diff[half - 1];
                cur = min(cur, sum_l * 4 + exp_inv(half) + exp_inv(sz - half));
            }

            int j = 0;
            for (int i = 0; i < n; i++){
                while (j < sz && pos[c][j] <= i) j++;
                cnt[i] += j;
            }

            tot += cur;

            if (tot > ans) break;
        }

        ans = min(ans, tot);


    } while (next_permutation(all(alphabet)));

    cout << fixed << setprecision(5);
    cout << (long double) ans / 4.0 << endl;

}

int main() {
    ios_base::sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    solve();

    return 0;
}

Compilation message (stderr)

passes.cpp: In function 'void solve()':
passes.cpp:23:21: warning: array subscript has type 'char' [-Wchar-subscripts]
   23 |         if (pos[s[i]].empty()) alphabet += s[i];
      |                     ^
passes.cpp:24:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   24 |         pos[s[i]].push_back(i);
      |                 ^
passes.cpp:43:32: warning: array subscript has type 'char' [-Wchar-subscripts]
   43 |             int sz = (int) pos[c].size();
      |                                ^
passes.cpp:45:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   45 |             for (int i : pos[c]){
      |                              ^
passes.cpp:62:38: warning: array subscript has type 'char' [-Wchar-subscripts]
   62 |                 while (j < sz && pos[c][j] <= i) j++;
      |                                      ^
passes.cpp:30:9: warning: unused variable 'm2' [-Wunused-variable]
   30 |     int m2 = m1 + 1;
      |         ^~

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