oj.uz

Submission #928447

# Submission time Handle Problem Language Result Execution time Memory
928447 2024-02-16T12:05:12 Z berr Boarding Passes (BOI22_passes) C++17
5 / 100
 198 ms 344584 KB 
//ᓚᘏᗢ
 
#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(val(mask, l+1, ne)<val(mask, l, ne)){
            l++;
            if(val(mask, l+1, ne)<val(mask, l, ne))
                l++;
        }

        if(val(mask, 0, ne)<val(mask, l, ne)) l=0;
        if(val(mask, g[ne].size(), ne) <val(mask, l, ne)) l=g[ne].size();

//        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)]+get(i^(1<<l), l));
            }
        }
    }
 //   cout<<dp[4];
    cout<<fixed<<setprecision(5)<<dp[(1<<15)-1];

}

Compilation message

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)
      |                    ~~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 64856 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 15 ms 58200 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 20 ms 59996 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 24 ms 59996 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 34 ms 64860 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 198 ms 306500 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 162 ms 335400 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 166 ms 344580 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 164 ms 344584 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 82520 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 31 ms 25736 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 110 ms 198816 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 117 ms 198748 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 86 ms 198748 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 77 ms 198748 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 120 ms 198832 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 84 ms 141652 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Incorrect 96 ms 198692 KB 1st numbers differ - expected: '56.0000000000', found: '50.5000000000', error = '0.0982142857'
10 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 82520 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 31 ms 25736 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 110 ms 198816 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 117 ms 198748 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 86 ms 198748 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 77 ms 198748 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 120 ms 198832 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 84 ms 141652 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Incorrect 96 ms 198692 KB 1st numbers differ - expected: '56.0000000000', found: '50.5000000000', error = '0.0982142857'
10 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 64856 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 15 ms 58200 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 20 ms 59996 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 24 ms 59996 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 34 ms 64860 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 198 ms 306500 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 162 ms 335400 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 166 ms 344580 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 164 ms 344584 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 34 ms 82520 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 31 ms 25736 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 110 ms 198816 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 117 ms 198748 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 86 ms 198748 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 77 ms 198748 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 120 ms 198832 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 84 ms 141652 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Incorrect 96 ms 198692 KB 1st numbers differ - expected: '56.0000000000', found: '50.5000000000', error = '0.0982142857'
19 Halted 0 ms 0 KB -