Submission #1205845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205845		lighton	Boarding Passes (BOI22_passes)	C++17	100 / 100	442 ms	13580 KiB

passes

#include<bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define forf(i,s,e) for(int i = s; i<=e; i++)
#define forb(i,s,e) for(int i = s; i>=e; i--)
#define idx(i,v) lower_bound(all(v),i)-v.begin()
#define comp(v) v.erase(unique(all(v)),v.end())
#define sz(v) (int)v.size()
#define fs first
#define se second
#define SP << " " <<
#define LN << "\n"
#define IO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
ll inf = 1e18;

int N,M; string S;
vector<char> chars;
vector<int> pos[16];
int G[100001];
vector<double> f[16][16];
double dp[1<<15];

double eval(int now, int bit, int idx){
    double ret = 0;
    forf(i,0,M-1){
        if(!(bit & ( 1<<i))) continue;
        if(i==now) ret += f[now][i][idx]/2;
        else ret += f[now][i][idx];
    }

    return ret;
}

double calc(int now, int bit){
    int l = -1, r = sz(f[now][now])-1;
    while(l+1<r){
        int m = l+r>>1;
        if(eval(now,bit,m) < eval(now,bit,m+1)) r = m;
        else l = m;
    }

    return eval(now,bit,r);
}

int main(){
    cin>>S; N = sz(S);
    forf(i,0,N-1) chars.pb(S[i]);
    sort(all(chars)), comp(chars);
    forf(i,0,N-1) G[i] = idx(S[i], chars), pos[G[i]].pb(i);
    M = sz(chars);

    forf(i,0,M-1){
        forf(j,0,M-1){
            f[i][j].resize(sz(pos[i])+1,0);
            for(auto u : pos[i]){
                f[i][j][0] += pos[j].end() - upper_bound(all(pos[j]), u);
            }
            int idx = 1;
            for(auto u : pos[i]){
                f[i][j][idx] = f[i][j][idx-1];
                f[i][j][idx] -= pos[j].end() - upper_bound(all(pos[j]),u);
                f[i][j][idx] += lower_bound(all(pos[j]), u) - pos[j].begin();
                idx++;
            }
        }
    }

    forf(i,1,(1<<M)-1) dp[i] = inf;
    forf(now,1,(1<<M)-1){
        forf(b,0,M-1){
            if(!(now&(1<<b))) continue;
            int prv = now^(1<<b);
            dp[now] = min(dp[now], dp[prv] + calc(b,now));
        }
    }

    cout.precision(100);
    cout<< dp[(1<<M)-1];
}

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