oj.uz

Submission #602649

# Submission time Handle Problem Language Result Execution time Memory
602649 2022-07-23T09:48:48 Z isaachew Boarding Passes (BOI22_passes) C++17
55 / 100
 97 ms 468 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=0;
    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;
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 296 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 300 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 304 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Incorrect 2 ms 468 KB 1st numbers differ - expected: '772893586.0000000000', found: '500000000.0000000000', error = '0.3530804123'
7 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 300 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 296 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 296 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 296 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 296 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 300 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 296 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 296 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 296 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 296 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 0 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 300 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 296 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 14 ms 212 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 12 ms 308 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 97 ms 316 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 74 ms 320 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 62 ms 312 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 57 ms 304 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 67 ms 312 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 65 ms 312 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 64 ms 212 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 65 ms 212 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 66 ms 312 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 65 ms 316 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 296 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 300 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 304 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Incorrect 2 ms 468 KB 1st numbers differ - expected: '772893586.0000000000', found: '500000000.0000000000', error = '0.3530804123'
7 Halted 0 ms 0 KB -