제출 #1179641

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1179641		tamyte	Boarding Passes (BOI22_passes)	C++20	30 / 100	20 ms	1916 KiB

passes

#include <bits/stdc++.h>
using namespace std;
using ll = long long;


double add(vector<int>& arr, vector<int>& points) {
	double exp = 0;
	int j = 0;
	for (auto& i : points) {
		int left = upper_bound(begin(arr), end(arr), i) - begin(arr);
		int right = arr.size() - left;
		double l = left + (1.0 * j / 2.0);
		double r = right + (points.size() - j - 1) / 2.0;
		exp += min(l, r);
		j++;
	}
	for (auto& i : points) {
		arr.push_back(i);
	}
	return exp;
}

int main(){
    // random_device rd;
    // mt19937 rng(rd());
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 	string s;
 	cin >> s;
 	int n = s.size();
 	vector<vector<int>> points(7);
 	vector<int> pool;
 	for (int i = 0; i < n; ++i) {
 		int j = s[i] - 'A';
 		pool.push_back(j);
 		points[j].push_back(i);
 	}
 	sort(begin(pool), end(pool));
 	pool.erase(unique(begin(pool), end(pool)), end(pool));
 	double res = 1e18;
 	do {
 		vector<int> now;
 		double curr = 0;
 		for (auto& u : pool) {
 			curr += add(now, points[u]);
 			sort(begin(now), end(now));
 		}
 		res = min(res, curr);
 	} while (next_permutation(begin(pool), end(pool)));
 	cout << fixed << setprecision(10) << res << endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 25 / 25
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40