Submission #1306614

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306614		DanielPr8	Boarding Passes (BOI22_passes)	C++20	100 / 100	388 ms	34252 KiB

passes

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvl = vector<vll>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;
using vd = vector<vector<pll>>;
#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(){
    ios_base::sync_with_stdio(0);cin.tie(NULL);
    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);
    vector<vvl> rs(m, vvl(m,{0}));
    vector<vvl> sf(m, vvl(m,{0}));
    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]){
                    rs[i][j].pb(2*S->que(0, h-1)+rs[i][j].back());
                }
                for(ll o = g[j].size()-1; o >= 0; --o){
                    ll h = g[j][o];
                    sf[i][j].pb(2*S->que(h+1, n-1)+sf[i][j].back());
                }
            }
            else{
                for(ll h:g[j]){
                    rs[i][j].pb(rs[i][j].back()+S->que(0, h-1));
                }
                for(ll o = g[j].size()-1; o >= 0; --o){
                    ll h = g[j][o];
                    sf[i][j].pb(sf[i][j].back()+S->que(h+1, n-1));
                }
            }
            reverse(all(sf[i][j]));
        }
        for(ll h: g[i])S->upd(h, -1);
    }

    vvl gtg(1<<m, vll(m));
    for(ll i = 0; i < (1<<m); ++i){
        for(ll j = 0; j < m; ++j){
            if(!(i & (1<<j)))continue;
            ll s=0, e=g[j].size();
            while(s<e){
                ll m1 = (2*s+e)/3;
                ll m2 = (s+e*2+1)/3;
                ll c1=0,c2=0;
                for(ll h = 0; h < m; ++h){
                    if(i&(1<<h)){
                        c1 += rs[h][j][m1]+sf[h][j][m1];
                        c2 += rs[h][j][m2]+sf[h][j][m2];
                    }
                }
                if(c1>c2)s=m1+1;
                else e=m2-1;
                gtg[i][j]=min(c1,c2);
            }
        }
    }

    vll 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) << (double)dp[(1<<m)-1]/2;
}

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