oj.uz

Submission #928452

# Submission time Handle Problem Language Result Execution time Memory
928452 2024-02-16T12:12:17 Z berr Boarding Passes (BOI22_passes) C++17
25 / 100
 2000 ms 306616 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(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

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)){
      |               ~~~^~~~~~~~~~~~~~
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 256 ms 64600 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 12 ms 58204 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 16 ms 59996 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 18 ms 59996 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 279 ms 64856 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2058 ms 306616 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 82524 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 50 ms 25692 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 96 ms 198740 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 86 ms 198712 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 77 ms 198708 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 50 ms 198736 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 87 ms 198748 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 58 ms 141656 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 68 ms 194612 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 66 ms 194648 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 63 ms 195040 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 71 ms 196696 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 67 ms 194640 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 66 ms 194644 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 63 ms 194584 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 64 ms 194640 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 66 ms 194648 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 82524 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 50 ms 25692 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 96 ms 198740 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 86 ms 198712 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 77 ms 198708 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 50 ms 198736 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 87 ms 198748 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 58 ms 141656 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 68 ms 194612 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 66 ms 194648 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 63 ms 195040 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 71 ms 196696 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 67 ms 194640 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 66 ms 194644 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 63 ms 194584 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 64 ms 194640 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 66 ms 194648 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 26 ms 82520 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 43 ms 25692 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 93 ms 198828 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 84 ms 198648 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 78 ms 198736 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 47 ms 198748 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 97 ms 198736 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 64 ms 141656 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 64 ms 198736 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 65 ms 198576 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 65 ms 198740 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 78 ms 198740 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 67 ms 198608 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 65 ms 198744 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 62 ms 198748 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 77 ms 198740 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 67 ms 198740 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Execution timed out 2056 ms 71888 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 64600 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 12 ms 58204 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 16 ms 59996 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 18 ms 59996 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 279 ms 64856 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2058 ms 306616 KB Time limit exceeded
7 Halted 0 ms 0 KB -