Submission #789008

#	Time	Username	Problem	Language	Result	Execution time	Memory
789008		Ozy	Boarding Passes (BOI22_passes)	C++17	0 / 100	2083 ms	340 KiB

passes

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << fixed << setprecision(1) << a << endl
#define debugsl(a) cout << #a << " = " << fixed << setprecision(1) << a << ", "
#define rep(i,a,b) for(int i = (a); i<=(b); i++)
#define repa(i,a,b) for(int i = (a); i>=(b); i--)
#define pll pair<lli,lli>

#define MAX 100000
#define G 7

lli n,k,arr[MAX+2],cont,p_[G+2],vis[G+2],sum[G+2];
long double dp[MAX+2],res,a;
string st;
map<char,lli> mapa;
vector<lli> orden;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> st;
    n = st.size();

    cont = 1;
    rep(i,1,n) {
        if (mapa.find((char)st[i-1]) == mapa.end()) mapa[(char)st[i-1]] = cont++;
        arr[i] = mapa[st[i-1]];

        a = (i-1);
        a /= 2;
        dp[i] = dp[i-1] + a;
    }

    res = -1;
    rep(mitad,1,n) {
        //debug(mitad);

        orden.clear();
        rep(i,1,G) orden.push_back(i);

        do {
            cont = 1;
            rep(i,0,G-1) {
                //debug(orden[i]);
                p_[orden[i]] = cont++;
            }

            long double sub_res = 0;
            rep(i,1,G) sum[i] = 0;
            rep(i,1,mitad-1) {
                rep(j,1,p_[arr[i]]-1) sub_res += sum[j];
                sum[p_[arr[i]]]++;
            }
            //debugsl(sub_res);
            rep(i,1,G) sub_res += dp[sum[i]];
            //debug(sub_res);

            rep(i,1,G) sum[i] = 0;
            repa(i,n,mitad) {
                rep(j,1,p_[arr[i]]-1) sub_res += sum[j];
                sum[p_[arr[i]]]++;
            }
            //debugsl(sub_res);
            rep(i,1,G) sub_res += dp[sum[i]];
            //debug(sub_res);
            if (res == -1 || sub_res < res) res = sub_res;

        } while (next_permutation(orden.begin(), orden.end()));
    }

    cout << fixed << setprecision(3) << res;

    return 0;
}

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