Submission #1181069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181069		tamyte	Boarding Passes (BOI22_passes)	C++20	100 / 100	191 ms	36716 KiB

passes

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

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(15);
 	vector<int> pool;
 	for (int i = 0; i < n; ++i) {
 		int j = s[i] - 'A';
 		pool.push_back(j);
 	}
 	sort(begin(pool), end(pool));
 	pool.erase(unique(begin(pool), end(pool)), end(pool));
 	map<char, int> mp;
 	for (int i = 0; i < pool.size(); ++i) {
 		mp[(pool[i] + 'A')] = i;
 	}
 	vector<vector<int>> cnt(15, vector<int>(n + 1));
 	for (int i = 0; i < n; ++i) {
 		points[mp[s[i]]].push_back(i);
 		for (int j = 0; j < 15; ++j) {
 			cnt[j][i + 1] = cnt[j][i] + (j == mp[s[i]]);
 		}
 	}
 	// for (int j = 0; j < 2; ++j) {
 		// for (int i = 0; i < n; ++i) {
 			// cout << cnt[j][i] << " ";
 		// }
 		// cout << endl;
 	// }
 	int k = pool.size();
 	vector<vector<double>> nxt((1 << k), vector<double>(k));
 	// cerr << "BEGIN:\n";
 	for (int i = 0; i < k; ++i) {
 		// cerr << "A\n";
 		auto v = points[i];
 		vector<vector<ll>> L(k, vector<ll>(v.size())), R(k, vector<ll>(v.size()));
 		for (int j = 0; j < k; ++j) {
 			for (int l = 0; l < v.size(); ++l) {
 				L[j][l] = cnt[j][v[l]];
 				if (l > 0) L[j][l] += L[j][l - 1];
 			}
 			for (int l = v.size() - 1; l >= 0; --l) {
 				R[j][l] = cnt[j][n] - cnt[j][v[l] + 1];
 				if (l + 1 < v.size()) R[j][l] += R[j][l + 1];
 			}
 		}
 		// cerr << "B\n";
 		for (int j = 0; j < (1 << k); ++j) {
 			if (j >> i & 1) continue;
 			auto calc = [&](ll l) -> double {
 				double res = 0;
 				for (int x = 0; x < k; ++x) {
 					if (j >> x & 1) {
 						if (l > 0) res += L[x][l - 1];
 						if (l < v.size()) res += R[x][l];
 					}
 				}
 				res += 1.0 * l * (l - 1) / 4.0;
 				ll r = v.size() - l;
 				res += 1.0 * r * (r - 1) / 4.0;
 				return res;
 			};
 			int l = 0, r = v.size();
 			while (l < r) {
 				int mid = (l + r) / 2;
 				if (calc(mid) > calc(mid + 1)) {
 					l = mid + 1;
 				} else {
 					r = mid;
 				}
 			}
 			nxt[j][i] = calc(l);
 		}
 		// cerr << "C\n";
 	}
 	// cerr << "END\n";
 	vector<double> dp((1 << k), 1e15);
 	dp[0] = 0;
 	for (int mask = 0; mask < (1 << k); ++mask) {
 		if (dp[mask] == 1e15) continue;
 		for (int j = 0; j < k; ++j) {
 			if (mask >> j & 1) continue;
 			// cout << "NOW = " << char(j + 'A') << "\n";
 			double ndp = dp[mask] + nxt[mask][j];
 			dp[mask | (1 << j)] = min(dp[mask | (1 << j)], ndp);
 		}
 	}
 	cout << fixed << setprecision(10) << dp[(1 << k) - 1] << endl;
}

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