oj.uz

Submission #928449

# Submission time Handle Problem Language Result Execution time Memory
928449 2024-02-16T12:08:32 Z berr Boarding Passes (BOI22_passes) C++17
0 / 100
 2000 ms 306444 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, 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)
      |                    ~~~^~~~~~~~~~~~~
passes.cpp: In lambda function:
passes.cpp:69:19: warning: unused variable 'r' [-Wunused-variable]
   69 |         int l= 0, r = g[ne].size();
      |                   ^
passes.cpp:70:13: warning: unused variable 'h' [-Wunused-variable]
   70 |         int h = 2000;
      |             ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 64604 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 17 ms 58204 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 19 ms 59996 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 21 ms 59996 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 283 ms 64860 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2043 ms 306444 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 82520 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 43 ms 25688 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 103 ms 198736 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 106 ms 198740 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 102 ms 198828 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 79 ms 198748 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 92 ms 198740 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 73 ms 141656 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Incorrect 83 ms 198740 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 29 ms 82520 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 43 ms 25688 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 103 ms 198736 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 106 ms 198740 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 102 ms 198828 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 79 ms 198748 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 92 ms 198740 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 73 ms 141656 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Incorrect 83 ms 198740 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 238 ms 64604 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 17 ms 58204 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 19 ms 59996 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 21 ms 59996 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 283 ms 64860 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2043 ms 306444 KB Time limit exceeded
7 Halted 0 ms 0 KB -