oj.uz

Submission #602647

# Submission time Handle Problem Language Result Execution time Memory
602647 2022-07-23T09:48:00 Z isaachew Boarding Passes (BOI22_passes) C++17
0 / 100
 483 ms 1048576 KB 
#include <bits/stdc++.h>
/*
 Up to G boarding groups
 ST1: Expected number of passes for a boarding group of k from one end = 1/2 * current boarding group
 ST2: Check every permutation
 ST3: O(2^G*n)
 
 60/100?
 */
int main(){
    std::string gs;
    std::cin>>gs;
    int g;
    int n=gs.size();
    std::vector<int> counts(26,0);
    for(char i:gs){
        g=std::max(g,i-'A'+1);
        counts[i-'A']++;
    }
    if(1){
        std::vector<int> mincost(1<<g,0);
        for(int i=1;i<1<<g;i++){
            int mcsf=1000000000;
            for(int j=0;j<g;j++){
                if(((i>>j)&1)==0)continue;
                //if(counts[j]==0)continue;
                //std::cout<<i<<'/'<<(char)(j+'A')<<'\n';
                int cind=i^(1<<j);
                int curcost=0;
                int totalcost=counts[j];//twice total
                int expcost=0;
                for(int r=0;r<g;r++){
                    if((cind>>r)&1){
                        totalcost+=counts[r]*2;
                    }
                }
                for(int k=0;k<n;k++){
                    int ln=gs[k]-'A';
                    if((cind>>ln)&1){
                        curcost+=2;
                    }
                    //std::cout<<curcost<<'/'<<totalcost-curcost-1<<' ';
                    if(ln==j){if(curcost*2>totalcost-1){
                        expcost+=totalcost-curcost-1;
                    }else{
                        expcost+=curcost;
                    }}
                    
                    if(ln==j){
                        curcost++;
                    }
                }
                //std::cout<<'\n';
                //std::cout<<"current "<<expcost<<", total "<<expcost+mincost[cind]<<'\n';
                mcsf=std::min(mcsf,expcost+mincost[cind]);
            }
            mincost[i]=mcsf;
        }
        int val=mincost[(1<<g)-1];
        std::cout<<val/2;
        if(val&1)std::cout<<".5";
        std::cout<<'\n';
        return 0;
    }
}

Compilation message

passes.cpp: In function 'int main()':
passes.cpp:13:9: warning: 'g' may be used uninitialized in this function [-Wmaybe-uninitialized]
   13 |     int g;
      |         ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 431 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 483 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 483 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 431 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -