Submission #735803

#	Time	Username	Problem	Language	Result	Execution time	Memory
735803		Victor	Boarding Passes (BOI22_passes)	C++17	100 / 100	241 ms	26252 KiB

passes

// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (ll i = (a); i < (b); ++i)
#define per(i, a, b) for (ll i = (b) - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) (ll)x.size()
#define pb push_back
#define mp make_pair
#define debug(x) cout<<#x<<" = "<<x<<endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const ll INF = 1'000'000'007;

// 2^g state DP, what groups have boarded
// g transitions, next group to board
// to find optimal boarding side for next group we do not need to to O(N) thing
// instead we go through each group and find how many are to the left when doing binary search
// we precompute tables for each group
// something like O(2^g * g² * log n)

const ll g=15;
ll n;
string s;
double memo[1<<g];
vll groups_sum[g];
vll groups_pos[g];
vll groups_cross[g][g];

double dp(ll mask) {
    if(mask==(1<<g)-1) return 0;

    double &ans=memo[mask];
    if(ans!=-1) return ans;

    ans=1e10;
    rep(i,0,g) if(!(mask&(1<<i))) {
        
        ll group_size=sz(groups_pos[i]);
        ll lo=0,hi=group_size;

        while(hi-lo>4) {
            ll mid=(lo+hi)/2;
            //cout<<"i = "<<i<<" mid = "<<mid<<endl;

            double res[]={0,0};
            rep(k,0,2) {
                rep(j,0,g) if(mask&(1<<j)) res[k]+=double(groups_cross[i][j][mid+k]);

                ll peopleL=mid+k,peopleR=(group_size)-peopleL;
                res[k]+=double(peopleL*(peopleL-1))/4.0+double(peopleR*(peopleR-1))/4.0;
            }
            
            //if(add==100800) cout<<"peopleL = "<<peopleL<<" peopleR = "<<peopleR<<endl;
        

            if(res[0]<res[1]) hi=mid;
            else lo=mid;
        }

        //cout<<"lo = "<<lo<<" hi = "<<hi<<endl;

        rep(k,lo,hi+1) {
            double add=0;
            rep(j,0,g) if(mask&(1<<j)) add+=double(groups_cross[i][j][k]);

            ll peopleL=k,peopleR=(group_size)-peopleL;
            add+=double(peopleL*(peopleL-1))/4.0+double(peopleR*(peopleR-1))/4.0;
            
            //if(add==100800) cout<<"peopleL = "<<peopleL<<" peopleR = "<<peopleR<<endl;
            ans=min(ans,dp(mask|(1<<i))+add);
        }
    }

    //cout<<"mask = "<<mask<<" ans = "<<ans<<endl;
    return ans;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    rep(i,0,1<<g) memo[i]=-1;
    cin>>s;

    n=sz(s);
    trav(chr,s) chr-='A';

    rep(i,0,g) groups_sum[i].assign(n+1,0);
    rep(i,0,n) {
        ++groups_sum[(ll)s[i]][i];
        groups_pos[(ll)s[i]].pb(i);
    }

    rep(i,0,g) rep(j,1,n) groups_sum[i][j]+=groups_sum[i][j-1];
    rep(i,0,g) rep(j,0,g) {
        ll val=0;
        groups_cross[i][j].pb(0);
        trav(pos,groups_pos[i]) {
            val+=groups_sum[j][pos];
            groups_cross[i][j].pb(val);
        }
        
        val=0;
        per(k,0,sz(groups_pos[i])) {
            ll pos=groups_pos[i][k];
            val+=sz(groups_pos[j])-groups_sum[j][pos];
            groups_cross[i][j][k]+=val;
        }
    }
    
    cout<<setprecision(20)<<dp(0)<<endl;
    return 0;
}   

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