# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
870134 | 2023-11-07T02:49:20 Z | Ahmed_Solyman | Boarding Passes (BOI22_passes) | C++14 | 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
# | 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' |
# | 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' |
# | 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 | - |
# | 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 | - |