oj.uz

Submission #602657

# Submission time Handle Problem Language Result Execution time Memory
602657 2022-07-23T09:54:35 Z isaachew Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 724 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<long long> mincost(1<<g,0);
        for(int i=1;i<1<<g;i++){
            long long mcsf=10000000000000000;
            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);
                long long curcost=0;
                long long totalcost=counts[j];//twice total
                long long 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;
        }
        long long val=mincost[(1<<g)-1];
        std::cout<<val/2;
        if(val&1)std::cout<<".5";
        std::cout<<'\n';
        return 0;
    }
}

Subtask #1
5.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 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 212 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 Correct 2 ms 468 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 596 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 3 ms 560 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 596 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 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 0 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 0 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 0 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 0 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 0 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 0 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 0 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 0 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 0 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 0 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 0 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 0 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 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 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 0 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 0 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 0 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 0 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 0 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 0 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 0 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 0 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 0 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 0 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 0 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 0 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 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 0 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 0 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 0 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 0 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 0 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 0 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 0 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 0 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 0 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 0 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 0 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 0 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 13 ms 212 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 13 ms 320 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 99 ms 320 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 54 ms 212 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 54 ms 212 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 54 ms 212 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 68 ms 212 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 70 ms 212 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 69 ms 304 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 70 ms 304 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 64 ms 308 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 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 212 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 Correct 2 ms 468 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 596 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 3 ms 560 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 596 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 0 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 0 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 0 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 0 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 0 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 0 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 0 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 0 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 0 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 0 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 0 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 0 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 0 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 0 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 0 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 0 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 0 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 0 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 0 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 0 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 0 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 0 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 0 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 0 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 0 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 13 ms 212 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 13 ms 320 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 99 ms 320 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 54 ms 212 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 54 ms 212 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 54 ms 212 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 68 ms 212 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 70 ms 212 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 69 ms 304 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 70 ms 304 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 64 ms 308 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 65 ms 316 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 18 ms 468 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 28 ms 568 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 0 ms 212 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 0 ms 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 4 ms 468 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 3 ms 452 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 3 ms 468 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 4 ms 468 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 0 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 0 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 0 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 0 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 0 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 0 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 0 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 0 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 0 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 0 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 0 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 0 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 14 ms 212 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 12 ms 212 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 108 ms 304 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 58 ms 300 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 60 ms 212 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 59 ms 308 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 68 ms 212 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 72 ms 300 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 65 ms 212 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 69 ms 212 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 69 ms 300 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 65 ms 212 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2080 ms 724 KB Time limit exceeded
97 Halted 0 ms 0 KB -