oj.uz

Submission #850423

# Submission time Handle Problem Language Result Execution time Memory
850423 2023-09-16T14:25:42 Z Ahmed57 Boarding Passes (BOI22_passes) C++17
60 / 100
 599 ms 40624 KB 
#include <bits/stdc++.h>
using namespace std;
int c = 0;
vector<int> arr[15];
short pref[10001][1024],suf[10001][1024];
long double dp[1024];
int sz;
long double ge(long double x){
    if(x<=1)return 0;
    return (x*(x-1))/4.0;
}
int main(){
    string s;cin>>s;
    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(ind);
        }else{
            arr[x[i]-1].push_back(ind);
        }
    }
    if(c==1){
        long long x = s.size();
    if(x<=2){
        cout<<0.0<<endl;return 0;
    }
    else if(x==3){
        cout<<0.5<<endl;
        return 0;
    }
    long double v1 = x/2 , v2 = x-v1;
    long double ans = ((v1*(v1-1)/2)*(v1*(v1-1)/2))/(v1*(v1-1));
    swap(v1,v2);
    ans+= ((v1*(v1-1)/2)*(v1*(v1-1)/2))/(v1*(v1-1));
    cout<<setprecision(3)<<fixed<<ans<<endl;
        return 0;
    }
    for(int mask = 0;mask<(1<<c);mask++){
        for(int i = 0;i<sz;i++){
            pref[i][mask] = (mask&(1<<(x[s[i]]-1))?1:0);
            if(i)pref[i][mask]+=pref[i-1][mask];
        }
        for(int i = sz-1;i>=0;i--){
            suf[i][mask] =(mask&(1<<(x[s[i]]-1))?1:0);
            if(i<sz-1)suf[i][mask]+=suf[i+1][mask];
        }
    }
    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))){
            long long all = 0 , xd = 0;
            for(int e = 0;e<arr[j].size();e++){
                all+=suf[arr[j][e]][mask];
            }
            dp[mask] = min(dp[mask],dp[mask^(1<<j)]+all+xd+ge(arr[j].size()));
            for(int e = 0;e<arr[j].size();e++){
                all-=suf[arr[j][e]][mask];
                xd+=pref[arr[j][e]][mask];
                dp[mask] = min(dp[mask],dp[mask^(1<<j)]+all+xd+ge(e+1)+ge(arr[j].size()-e-1));
            }
        }
    }
    }
    cout<<setprecision(4)<<fixed<<dp[0]<<endl;
    return 0;
}

Compilation message

passes.cpp: In function 'int main()':
passes.cpp:61:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             for(int e = 0;e<arr[j].size();e++){
      |                           ~^~~~~~~~~~~~~~
passes.cpp:65:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             for(int e = 0;e<arr[j].size();e++){
      |                           ~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 600 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 984 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 3 ms 1248 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 1236 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 3 ms 1240 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 4700 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 4700 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 4700 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 2396 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 4700 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 2396 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 2396 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 2396 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 2552 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 2396 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 2396 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 2396 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 2396 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 2396 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 2396 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 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 4700 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 4700 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 4700 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 2396 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 4700 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 2396 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 2396 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 2396 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 2552 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 2396 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 2396 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 2396 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 2396 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 2396 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 2396 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 4700 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 4700 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 4700 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 2396 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 4700 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 2396 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 2392 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 2396 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 2396 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 2396 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 2396 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 2396 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 2396 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 2396 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 2396 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 348 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 344 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 599 ms 40588 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 287 ms 40564 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 297 ms 40624 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 311 ms 40496 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 422 ms 40276 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 413 ms 40180 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 427 ms 40436 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 407 ms 40028 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 406 ms 40180 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 399 ms 40180 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 348 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 600 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 984 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 3 ms 1248 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 1236 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 3 ms 1240 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 4700 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 4700 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 4700 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 2396 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 4700 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 2396 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 2396 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 2396 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 2552 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 2396 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 2396 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 2396 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 2396 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 2396 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 2396 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 4700 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 4700 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 4700 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 2396 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 4700 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 2396 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 2392 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 2396 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 2396 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 2396 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 2396 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 2396 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 2396 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 2396 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 2396 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 ms 348 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1 ms 344 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 599 ms 40588 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 287 ms 40564 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 297 ms 40624 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 311 ms 40496 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 422 ms 40276 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 413 ms 40180 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 427 ms 40436 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 407 ms 40028 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 406 ms 40180 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 399 ms 40180 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 1 ms 2396 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Incorrect 20 ms 4652 KB 1st numbers differ - expected: '0.0000000000', found: '-486280.0000000000', error = '486280.0000000000'
58 Halted 0 ms 0 KB -