Submission #928454

#	Time	Username	Problem	Language	Result	Execution time	Memory
928454		berr	Boarding Passes (BOI22_passes)	C++17	100 / 100	679 ms	359340 KiB

passes

//ᓚᘏᗢ
 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int pr[15][15][100000];
int sf[15][15][100000];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    string s; cin >> s;
    vector<vector<int>> g(15);

    int n = s.size();
    for(int i=0; i<n; i++){
        g[s[i]-'A'].push_back(i);
    }

    vector pref(15, vector(n, 0));

    for(int i=0; i<15; i++){
        for(int l=0; l<15; l++){
            if(i==l) continue;

            for(auto u: g[i]){
                pr[l][i][u]=1;
                sf[l][i][u]=1;
            }

            for(int j=1; j<n; j++){
                pr[l][i][j]+=pr[l][i][j-1];
                sf[l][i][n-j-1]+=sf[l][i][n-j];                
            }
            int s = g[l].size();
            for(int j=1; j<s; j++){
                pr[l][i][g[l][j]]+=pr[l][i][g[l][j-1]];
                sf[l][i][g[l][s-j-1]]+=sf[l][i][g[l][s-j]];
            }
        }
    }

    vector dp(1<<15, 1e18);

    dp[0] = 0;

    auto pf=[&](int x){

        return (double)((double)x*(double)(x-1))/(double)4.0;
    };
    auto val =[&](int mask, int pos, int ne){

      //  return (0.0);
        double ans = 0;
        for(int i=0; i<15; i++){
            if((1<<i)&mask){
                if(pos-1>=0&&pos-1<g[ne].size())
                ans+=pr[ne][i][g[ne][pos-1]];
                if(pos<g[ne].size()&&pos>=0)
                ans+=sf[ne][i][g[ne][pos]];
            }
        }   

        return (double)pf(pos)+(double)pf(g[ne].size()-pos)+(double)ans;
    };

    auto get =[&](int mask, int ne){
        int l= 0, r = g[ne].size();
        int h = 2000;
        if(g[ne].size()==0) return 0.0;

        while(h--&&l+2<r){
            int m1 = l+(r-l)/3; int m2 = r-(r-l)/3;
            double val1 = val(mask, m1, ne); double val2 = val(mask, m2, ne);
          //  if(mask==0&&ne==2) cout<<l<<" "<<r<<"\n";

            if(val1 < val2) r = m2;
            else l = m1;
        }
        
        while(l+1<=g[ne].size()&&val(mask, l+1, ne)<val(mask, l, ne)){
            l++;
        }

//        if(mask==0&&ne==2) cout<<l<<" "<<r<<" "<<val(mask, 0, ne)<<" "<<val(mask, 1, ne)<<"\n";
        return val(mask, l, ne);
    };
    
    for(int i=1; i<(1<<15); i++){
        for(int l=0; l<15; l++){
            if((1<<l)&i){
                dp[i]=min(dp[i], dp[i^(1<<l)]+(double)get(i^(1<<l), l));
            }
        }
    }
 //   cout<<dp[4];
    cout<<fixed<<setprecision(5)<<dp[(1<<15)-1];

}

Compilation message (stderr)

passes.cpp: In lambda function:
passes.cpp:58:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |                 if(pos-1>=0&&pos-1<g[ne].size())
      |                              ~~~~~^~~~~~~~~~~~~
passes.cpp:60:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |                 if(pos<g[ne].size()&&pos>=0)
      |                    ~~~^~~~~~~~~~~~~
passes.cpp: In lambda function:
passes.cpp:82:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         while(l+1<=g[ne].size()&&val(mask, l+1, ne)<val(mask, l, ne)){
      |               ~~~^~~~~~~~~~~~~~

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