Submission #1164187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164187		handlebred	Boarding Passes (BOI22_passes)	C++20	100 / 100	163 ms	23124 KiB

passes

#include<bits/stdc++.h>
using namespace std;

#define REP(i,q) for(int i=0; i<(q); ++i)
#define FOR(i,p,q) for(int i=(p); i<=(q); ++i)
#define ROF(i,q,p) for(int i=(q); i>=(p); --i)
#define V vector
#define pb push_back
#define Co const
#define fi first
#define se seconda
#define as assign
#define rz resize
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
#define sz(V) (int)(V.size())
#define ckmin(a,b) a=min(a,b)
#define ckmax(a,b) a=max(a,b)
typedef long double ld;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#ifndef UNCLE
 typedef basic_string<bool> vb;
 typedef basic_string<int> vi;
 typedef basic_string<ll> vl;
#else
 typedef V<bool> vb;
 typedef V<int> vi;
 typedef V<ll> vl;
#endif

constexpr ll INFL=(ll)1e18;
int N,G=0;
V<vi> colVc;

void Input(){
    string s;
    cin>>s;
    N=sz(s);
    colVc.rz(40);
    vi col(40,-1);
    REP(i,N){
        if(col[s[i]-'A']==-1) col[s[i]-'A']=G++;
        colVc[col[s[i]-'A']].pb(i);
    }
}
void Solve(){
    V<V<vl>> qtP(G,V(G,vl())), qtS(G,V(G,vl()));
    REP(g1,G) REP(g2,G) if(g1!=g2){
        int j=0;
        qtP[g1][g2].as(sz(colVc[g2])+1,0), qtS[g1][g2].as(sz(colVc[g2])+1,0);
        REP(i,sz(colVc[g2])){
            while(j<sz(colVc[g1])&&colVc[g1][j]<colVc[g2][i]) ++j;
            qtP[g1][g2][i+1]=qtP[g1][g2][i]+j;
        }
        j=sz(colVc[g1])-1;
        ROF(i,sz(colVc[g2])-1,0){
            while(j>=0&&colVc[g1][j]>colVc[g2][i]) --j;
            qtS[g1][g2][i]=qtS[g1][g2][i+1]+sz(colVc[g1])-j-1;
        }
    }
    vl dp(1<<G,INFL);
    dp[0]=0;
    FOR(cmsk,0,(1<<G)-2){
        REP(gn,G) if(!(cmsk&(1<<gn))){
            int p=0,m,q=sz(colVc[gn])-1;
            auto GtQt=[&](Co int v){
                ll pro=(((ll)v-1)*v+((ll)sz(colVc[gn])-v-1)*(sz(colVc[gn])-v))/2;
                REP(gp,G) if(cmsk&(1<<gp)) pro+=2*(qtP[gp][gn][v]+qtS[gp][gn][v]);
                return pro;
            };
            while(p<=q){
                m=(p+q)/2;
                if(GtQt(m)<GtQt(m+1)) q=m-1;
                else p=m+1;
            }
            m=q+1;
            // ll v=dp[cmsk]+GtQt(m);
            ckmin(dp[cmsk|(1<<gn)],dp[cmsk]+GtQt(m));
        }
    }
    cout<<dp[(1<<G)-1]/2;
    if(dp[(1<<G)-1]&1) cout<<".5";
    cout<<"\n";
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    Input();
    Solve();
}

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