# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
868021 | 2023-10-30T08:32:53 Z | TAhmed33 | Boarding Passes (BOI22_passes) | C++ | 2000 ms | 1344 KB |
#include <bits/stdc++.h> using namespace std; typedef long double ld; typedef long long ll; string s; int n; vector <int> pos[26]; int main () { cin >> s; n = s.length(); for (int i = 0; i < n; i++) { pos[s[i] - 'A'].push_back(i); } int x = 0; for (int i = 1; i < 26; i++) if (!pos[i].empty()) x = i; vector <int> dd; ld mn = 1e18; for (int i = 0; i <= x; i++) if (!pos[i].empty()) dd.push_back(i); do { ld sum = 0; for (int i = 0; i < (int)dd.size(); i++) { int m = pos[dd[i]].size(); for (int j = 0; j < m; j++) { ld cnt = j; ld cnt2 = m - j - 1; ld cnt3 = 0, cnt4 = 0; for (int k = 0; k < i; k++) { for (auto l : pos[dd[k]]) { if (l < pos[dd[i]][j]) { cnt3++; } else { cnt4++; } } } sum += min(cnt * 0.5 + cnt3, cnt2 * 0.5 + cnt4); } } mn = min(mn, sum); } while (next_permutation(dd.begin(), dd.end())); cout << fixed << setprecision(6) << mn << '\n'; }
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 600 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 | 432 KB | found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
6 | Correct | 2 ms | 1240 KB | found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000' |
7 | Correct | 2 ms | 1216 KB | found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000' |
8 | Correct | 3 ms | 1240 KB | found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000' |
9 | Correct | 2 ms | 1344 KB | found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000' |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 | Correct | 0 ms | 428 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 | Correct | 34 ms | 600 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
4 | Correct | 26 ms | 428 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 | 432 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
8 | Correct | 1 ms | 348 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
9 | Correct | 6 ms | 432 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
10 | Correct | 5 ms | 348 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
11 | Correct | 4 ms | 348 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
12 | Correct | 5 ms | 344 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
13 | Correct | 5 ms | 348 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
14 | Correct | 6 ms | 348 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
15 | Correct | 5 ms | 348 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
16 | Correct | 5 ms | 436 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
17 | Correct | 5 ms | 348 KB | found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 | Correct | 0 ms | 428 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 | Correct | 34 ms | 600 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
4 | Correct | 26 ms | 428 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 | 432 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
8 | Correct | 1 ms | 348 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
9 | Correct | 6 ms | 432 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
10 | Correct | 5 ms | 348 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
11 | Correct | 4 ms | 348 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
12 | Correct | 5 ms | 344 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
13 | Correct | 5 ms | 348 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
14 | Correct | 6 ms | 348 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
15 | Correct | 5 ms | 348 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
16 | Correct | 5 ms | 436 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
17 | Correct | 5 ms | 348 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 | 29 ms | 412 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
21 | Correct | 26 ms | 352 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
22 | Correct | 6 ms | 348 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
23 | Correct | 1 ms | 352 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
24 | Correct | 20 ms | 436 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
25 | Correct | 1 ms | 348 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
26 | Correct | 5 ms | 500 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
27 | Correct | 5 ms | 344 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
28 | Correct | 4 ms | 348 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
29 | Correct | 5 ms | 348 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
30 | Correct | 4 ms | 432 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
31 | Correct | 5 ms | 352 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
32 | Correct | 4 ms | 552 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
33 | Correct | 5 ms | 344 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
34 | Correct | 5 ms | 348 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 | 348 KB | found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000' |
37 | Execution timed out | 2070 ms | 348 KB | Time limit exceeded |
38 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 600 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 | 432 KB | found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
6 | Correct | 2 ms | 1240 KB | found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000' |
7 | Correct | 2 ms | 1216 KB | found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000' |
8 | Correct | 3 ms | 1240 KB | found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000' |
9 | Correct | 2 ms | 1344 KB | found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000' |
10 | Correct | 1 ms | 348 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
11 | Correct | 0 ms | 428 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
12 | Correct | 34 ms | 600 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
13 | Correct | 26 ms | 428 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 | 432 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
17 | Correct | 1 ms | 348 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
18 | Correct | 6 ms | 432 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
19 | Correct | 5 ms | 348 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
20 | Correct | 4 ms | 348 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
21 | Correct | 5 ms | 344 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
22 | Correct | 5 ms | 348 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
23 | Correct | 6 ms | 348 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
24 | Correct | 5 ms | 348 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
25 | Correct | 5 ms | 436 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
26 | Correct | 5 ms | 348 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 | 29 ms | 412 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
30 | Correct | 26 ms | 352 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
31 | Correct | 6 ms | 348 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
32 | Correct | 1 ms | 352 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
33 | Correct | 20 ms | 436 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
34 | Correct | 1 ms | 348 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
35 | Correct | 5 ms | 500 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
36 | Correct | 5 ms | 344 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
37 | Correct | 4 ms | 348 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
38 | Correct | 5 ms | 348 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
39 | Correct | 4 ms | 432 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
40 | Correct | 5 ms | 352 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
41 | Correct | 4 ms | 552 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
42 | Correct | 5 ms | 344 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
43 | Correct | 5 ms | 348 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 | 348 KB | found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000' |
46 | Execution timed out | 2070 ms | 348 KB | Time limit exceeded |
47 | Halted | 0 ms | 0 KB | - |