oj.uz

Submission #870134

# Submission time Handle Problem Language Result Execution time Memory
870134 2023-11-07T02:49:20 Z Ahmed_Solyman Boarding Passes (BOI22_passes) C++14
30 / 100
 2000 ms 1308 KB 
/*
In the name of Allah
made by: Ahmed_Solyman
*/
#include <bits/stdc++.h>
#include <ext/rope>
 
using namespace std;
using namespace __gnu_cxx;
#pragma GCC optimize("-Ofast")
#pragma GCC optimize("-O1")
//-------------------------------------------------------------//
typedef long long ll;
typedef unsigned long long ull;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define PI acos(-1)
#define lb lower_bound
#define ub upper_bound
#define endl '\n'
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define sum_to(n) (n*(n+1))/2
#define pb push_back
#define pf push_front
#define fil(arr,x) memset(arr,x,sizeof(arr))
const ll mod=1e9+7;
int dx[8]={0,1,0,-1,1,1,-1,-1};
int dy[8]={1,0,-1,0,1,-1,-1,1};
//-------------------------------------------------------------//
ll lcm(ll a,ll b)
{
    return (max(a,b)/__gcd(a,b))*min(a,b);
}
void person_bool(bool x)
{
    cout<<(x?"YES":"NO")<<endl;
}
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    #ifndef ONLINE_JUDGE
    //freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
    #endif
    fast
    string s;cin>>s;
    vector<int>g[15];
    int i=0;
    int mx=0;
    for(char c:s){
        mx=max(mx,c-'A');
        g[c-'A'].push_back(i++);
    }
    vector<int>v;
    for(int i=0;i<=mx;i++)v.push_back(i);
    double ans=4e18;
    do{
        double p=0;
        for(int c=0;c<=mx;c++){
            for(int j=0;j<g[v[c]].size();j++){
                int a=0,b=0;
                for(int k=0;k<c;k++){
                    for(auto h:g[v[k]]){
                        a+=h<g[v[c]][j];
                        b+=h>g[v[c]][j];
                    }
                }
                p+=min(a+j/2.0,b+(g[v[c]].size()-j-1)/2.0);
            }
        }
        ans=min(ans,p);
    }while(next_permutation(all(v)));
    cout<<fixed<<setprecision(6)<<ans<<" ";
    return 0;
}

Compilation message

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

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 600 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 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 1 ms 1308 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 1 ms 1308 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 1 ms 1308 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 1 ms 1308 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 348 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 26 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 27 ms 432 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 6 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 20 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 3 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 3 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 3 ms 600 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 3 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 3 ms 460 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 3 ms 344 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 3 ms 344 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 3 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 3 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 3 ms 344 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 26 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 27 ms 432 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 6 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 20 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 3 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 3 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 3 ms 600 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 3 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 3 ms 460 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 3 ms 344 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 3 ms 344 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 3 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 3 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 3 ms 344 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 ms 348 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 26 ms 456 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 26 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 6 ms 460 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 344 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 20 ms 452 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 3 ms 452 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 3 ms 344 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 3 ms 344 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 3 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 3 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 3 ms 344 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 3 ms 504 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 3 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 3 ms 600 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 3 ms 344 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1758 ms 580 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1754 ms 568 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Execution timed out 2063 ms 348 KB Time limit exceeded
38 Halted 0 ms 0 KB -

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 600 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 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 1 ms 1308 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 1 ms 1308 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 1 ms 1308 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 1 ms 1308 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 0 ms 348 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 26 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 27 ms 432 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 6 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 20 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 3 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 3 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 3 ms 600 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 3 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 3 ms 460 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 3 ms 344 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 3 ms 344 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 3 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 3 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 3 ms 344 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 0 ms 348 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 26 ms 456 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 26 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 6 ms 460 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 344 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 20 ms 452 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 3 ms 452 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 3 ms 344 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 3 ms 344 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 3 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 3 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 3 ms 344 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 3 ms 504 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 3 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 3 ms 600 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 3 ms 344 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1758 ms 580 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1754 ms 568 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Execution timed out 2063 ms 348 KB Time limit exceeded
47 Halted 0 ms 0 KB -