Submission #1187155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187155		DanielPr8	Boarding Passes (BOI22_passes)	C++20	60 / 100	2096 ms	30224 KiB

passes

#include <bits/stdc++.h>
using namespace std;
using ll = int;
using vll = vector<ll>;
using vvl = vector<vll>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;
using pd = pair<double, double>;
using vd = vector<vector<pd>>;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()
struct seg{
    ll n;
    vll bl;
    seg(ll n):n(n){
        bl = vll(n*2);
    }
    void upd(ll i, ll x){
        i+=n;
        bl[i]+=x;
        for(i/=2;i>0;i/=2){
            bl[i] = bl[i*2]+bl[i*2+1];
        }
    }
    ll que(ll a, ll b){
        ll ans = 0;
        for(a+=n,b+=n;a<=b;a/=2, b/=2){
            if(a&1)ans += bl[a++];
            if(!(b&1))ans += bl[b--];
        }
        return ans;
    }
};
ll m=0;
int main(){
    string s;
    cin >> s;
    ll n = s.size();
    vll ch(26,-1);
    for(char i:s){
        if(ch[i-'A']==-1){
            ch[i-'A']=m++;
        }
    }
    vvl g(m);
    for(ll i = 0; i < n; ++i){
        g[ch[s[i]-'A']].pb(i);
    }
    ll N = 1 << (32-__builtin_clz(n-1));
    seg *S = new seg(N);
    vd tb(m, vector<pd>(n));
    for(ll i = 0; i < m; ++i){
        for(ll h: g[i])S->upd(h, 1);
        for(ll j = 0; j < m; ++j){
            if(i!=j){
                for(ll h:g[j]){
                    tb[i][h].f += S->que(0, h-1);
                    tb[i][h].s += S->que(h+1, n-1);
                }
            }
            else{
                for(ll h:g[j]){
                    tb[i][h].f += double(S->que(0, h-1))/2;
                    tb[i][h].s += double(S->que(h+1, n-1))/2;
                }
            }
        }
        for(ll h: g[i])S->upd(h, -1);
    }

    vector<vector<double>> gtg(1<<m, vector<double>(m));
    for(ll i = 0; i < (1<<m); ++i){
        for(ll j = 0; j < m; ++j){
            if(!(i & (1<<j)))continue;
            for(ll k:g[j]){
                pd tr = {0,0};
                for(ll h = 0; h < m; ++h){
                    if(!(i & (1<<h)))continue;
                    tr.f += tb[h][k].f;
                    tr.s += tb[h][k].s;
                }
                gtg[i][j] += min(tr.f, tr.s);
            }
        }
    }

    vector<double> dp(1<<m, 1e11);
    dp[0]=0;
    for(ll i = 1; i < (1<<m); ++i){
        for(ll j = 0; j < m; ++j){
            if(i & (1<<j)){
                dp[i] = min(dp[i], dp[i ^ (1<<j)] + gtg[i][j]);
            }
        }
    }
    cout << fixed << setprecision(6) << dp[(1<<m)-1];
}

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