Submission #1305042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305042		OgradL	Boarding Passes (BOI22_passes)	C++20	100 / 100	308 ms	183368 KiB

passes

#include <functional>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

void bucket_sort(int M, vector<int>& arr, function<int(int)> cmp){
	vector<vector<int>> buckets(M);

	for (int x : arr){
		buckets[cmp(x)].push_back(x);
	}

	int idx = 0;
	for (int i = 0; i < M; i++){
		for (int x : buckets[i]){
			arr[idx++] = x;
		}
	}
}

const int G = 15;
vector<vector<int>> pos;
vector<vector<vector<int>>> prefs;
vector<vector<vector<int>>> suffs;

long long calc(long long front, int i, int m){
	int split = 0;

	if (front < pos[i].size())
		split = pos[i][front];
	else
		split = pos[i][front-1]+1;

	long long back = (int)pos[i].size() - front;

	long long ans = 0;
	for (int b = 0; b < G; b++){
		if (b == i)
			continue;
		if ((m & (1 << b)) == 0)
			continue;
		ans += prefs[i][b][split] + suffs[i][b][split];
	}
	ans *= 2;
	ans += front * (front - 1) / 2;
	ans += back * (back - 1) / 2;
	return ans;
};

long long cost(int i, int m){
	if (pos[i].size() == 0)
		return 0;

	int lo = 0, hi = pos[i].size(), mid;
	while (lo + 1 < hi){
		mid = (lo + hi) / 2;

		if (calc(mid, i, m) > calc(mid+1, i, m)){
			lo = mid+1;
		} else {
			hi = mid;
		}
	}

	long long res = min(calc(lo, i, m), calc(hi, i, m));

	return res;
};

int main(){

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	string S;
	cin >> S;

	int N = S.size();

	pos.assign(G, vector<int>());
	prefs.assign(G, vector<vector<int>>(G, vector<int>(N+1, 0)));
	suffs.assign(G, vector<vector<int>>(G, vector<int>(N+1, 0)));

	for (int i = 0; i < N; i++){
		pos[S[i] - 'A'].push_back(i);
	}

	for (int i = 0; i < G; i++){
		for (int j = 0; j < G; j++){
			if (j == i)
				continue;
			int cnt_j = 0;
			prefs[i][j][0] = 0;
			for (int i0 = 0; i0 < N; i0++){
				long long c = 0;
				if (S[i0] == 'A' + j){
					cnt_j++;
				}
				if (S[i0] == 'A' + i){
					c = cnt_j;
				}
				prefs[i][j][i0+1] = prefs[i][j][i0] + c;
			}

			cnt_j = 0;
			suffs[i][j][N] = 0;
			for (int i0 = N-1; i0 >= 0; i0--){
				long long c = 0;
				if (S[i0] == 'A' + j){
					cnt_j++;
				}
				if (S[i0] == 'A' + i){
					c = cnt_j;
				}
				suffs[i][j][i0] = suffs[i][j][i0+1] + c;
			}
		}
	}


	vector<int> masks(1 << G);
	iota(masks.begin(), masks.end(), 0);

	bucket_sort(G+1, masks, [](int mask){
		return __builtin_popcount(mask);
	});

	vector<long long> dp(1 << G, 1e18);
	dp[0] = 0;

	for (int mask : masks){
		for (int i = 0; i < G; i++){
			if (mask & (1 << i))
				continue;

			long long c = cost(i, mask);

			dp[mask | (1 << i)] = min(dp[mask | (1 << i)], dp[mask] + c);
		}
	}

	long long ans = dp[(1 << G) - 1];
	cout << ans / 2 << ((ans & 1) ? ".5" : "") << "\n";
	
	return 0;
}

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