oj.uz

Submission #868021

# Submission time Handle Problem Language Result Execution time Memory
868021 2023-10-30T08:32:53 Z TAhmed33 Boarding Passes (BOI22_passes) C++
30 / 100
 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';
}

Subtask #1
5.0 / 5.0

# 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'

Subtask #2
25.0 / 25.0

# 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'

Subtask #3
0 / 30.0

# 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 -

Subtask #4
0 / 40.0

# 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 -