oj.uz

Submission #851327

# Submission time Handle Problem Language Result Execution time Memory
851327 2023-09-19T14:57:44 Z Ahmed57 Boarding Passes (BOI22_passes) C++17
55 / 100
 53 ms 54144 KB 
#include <bits/stdc++.h>
using namespace std;
int c = 0;
vector<int> arr[15];
int lol[15][15][100001];
int pref[100001],suf[100001];
int dp[(1<<15)];
int sz;

int main(){
    string s;cin>>s;
    int n = s.size();
    map<char,int> x;
    int ind = -1;
    sz = s.size();
    for(auto i:s){
        ind++;
        if(x[i]==0){
            x[i] = ++c;
            arr[c-1].push_back(0);
            arr[c-1].push_back(ind);
        }else{
            arr[x[i]-1].push_back(ind);
        }
    }
    for(int i = 0;i<c;i++){
        for(int j = 0;j<c;j++){
            int add = 2-(i==j) , cnt = 0;
            for(int e = 0;e<n;e++){
                pref[e] = (e?pref[e-1]:0)+((x[s[e]]-1)==i?cnt:0);
                cnt+=(x[s[e]]-1==j?add:0);
            }
            cnt = 0;
            for(int e = n-1;e>=0;e--){
                suf[e] = (e<n-1?suf[e+1]:0)+((x[s[e]]-1)==i?cnt:0);
                cnt+=(x[s[e]]-1==j?add:0);
            }
            for(auto d:arr[i]){
                lol[i][j][d] = pref[d]+suf[d+1];
                //cout<<lol[i][j][d]<<" "<<i<<" "<<j<<" "<<d<<endl;
            }
        }
    }
    for(int mask = (1<<c)-1;mask>=0;mask--){
    if(mask==(1<<c)-1){
        dp[mask] = 0;
        continue;
    }
    dp[mask] = 1000000000.0;
    for(int j = 0;j<c;j++){
        if(!(mask&(1<<j))){
            int l=0,r=arr[j].size()-1;
            while(l<r){
                int mid = (l+r)/2;
                int an = 0;
                for(int i=0;i<c;i++)if(!(mask&(1<<i)))an+=lol[j][i][arr[j][mid+1]]-lol[j][i][arr[j][mid]];
                if(an>=0)r = mid;
                else l = mid+1;
            }
            int an = 0;
            for(int i=0;i<c;i++)if(!((mask&(1<<i))))an+=lol[j][i][arr[j][l]];
            dp[mask] = min(dp[mask],dp[mask^(1<<j)]+an);
        }
    }
    }
    cout<<setprecision(4)<<fixed<<dp[0]/2.l<<endl;
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 2396 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Incorrect 4 ms 2900 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 4440 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 2392 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 4 ms 31064 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 3 ms 31068 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 4 ms 31064 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 3 ms 31064 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 4 ms 31064 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 3 ms 24924 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 4 ms 31176 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 4 ms 31068 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 4 ms 31068 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 3 ms 31068 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 4 ms 31068 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 3 ms 31068 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 4 ms 31068 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 3 ms 31068 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 4 ms 31068 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 4440 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 2392 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 4 ms 31064 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 3 ms 31068 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 4 ms 31064 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 3 ms 31064 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 4 ms 31064 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 3 ms 24924 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 4 ms 31176 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 4 ms 31068 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 4 ms 31068 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 3 ms 31068 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 4 ms 31068 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 3 ms 31068 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 4 ms 31068 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 3 ms 31068 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 4 ms 31068 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 4520 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 2492 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 4 ms 31068 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 4 ms 31208 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 4 ms 31068 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 3 ms 31216 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 4 ms 31232 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 3 ms 24920 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 3 ms 31068 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 4 ms 31064 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 4 ms 31068 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 3 ms 31212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 3 ms 31068 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 3 ms 31068 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 4 ms 31068 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 4 ms 31216 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 4 ms 31068 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 2652 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 2652 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 53 ms 53892 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 23 ms 54144 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 19 ms 53848 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 24 ms 53848 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 29 ms 53840 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 29 ms 53856 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 29 ms 53852 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 29 ms 53840 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 29 ms 53852 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 28 ms 53924 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

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