Submission #921283

#TimeUsernameProblemLanguageResultExecution timeMemory
921283themm1Boarding Passes (BOI22_passes)C++17
100 / 100
627 ms38596 KiB
#include <bits/stdc++.h> using namespace std; // ordered set whith s.order_of_key(x) method, which returns rank of element x in set s /* #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; */ // pair printing template <class T, class U> ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "(" << par.first << "; " << par.second << ")"; return out;} // set printing template <class T> ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for(const auto &x:cont) out << x << ", "; out << "}"; return out; } // map printing template <class T, class U> ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for(const auto &x:cont) out << x << ", "; out << "}"; return out; } // unordered_set printing template <class T> ostream& operator<<(ostream& out, const unordered_set<T> &cont) {out << "{";for(const auto &x:cont) out << x << ", ";out << "}";return out;} // unordered_map printing template <class T, class U> ostream& operator<<(ostream& out, const unordered_map<T, U> &cont) {out << "{";for(const auto &x:cont) out << x << ", ";out << "}";return out;} // vector printing template<class T> ostream& operator<<(ostream& out, const vector<T> &cont){ out << "["; for (const auto &x:cont) out << x << ", "; out << "]"; return out;} #define print(x) cout << (x) << endl; #define dmp(x) cerr << #x << " = " << x << endl #define dmpn(x) cerr << #x << " = " << x << "; " #define dmpl(x) cerr << "Line " << __LINE__ << ": " << #x << " = " << x << endl #define int long long using ll = long long; using ld = long double; using pii = pair<int, int>; using pll = pair<ll, ll>; #define pb push_back #define ff first #define ss second #define all(x) begin(x), end(x) #define sz(x) (int)x.size() #define contains(s,x) ((s).find(x) != (s).end()) const int MOD = 998244353; bool ith_bit(int x, int i) { int y = (1 << i); return (x ^ y) < x; } void print_bits(int x) { bitset<8> bx = x; cout << bx << endl; } vector<int> transform_input(string &s) { vector<int> mapping(26, -1); int cnt = 0; vector<int> a(sz(s), -1); for (int i = 0; i < sz(s); i++) { if (mapping[s[i] - 'A'] == -1) { mapping[s[i] - 'A'] = cnt; cnt++; } a[i] = mapping[s[i] - 'A']; } return a; } void solve() { string s; cin >> s; int N = sz(s); vector<int> arr = transform_input(s); int M = *max_element(all(arr)) + 1, M2 = (1 << M); vector<vector<int>> indices(M, vector<int>({-1})); for (int i = 0; i < N; i++) indices[arr[i]].pb(i); for (int k = 0; k < M; k++) indices[k].pb(N); vector<vector<int>> psums(M, vector<int>(N + 1, 0)); vector<vector<int>> pref_vals(M, vector<int>(N + 1, 0)), suff_vals(M, vector<int>(N + 1, 0)); for (int k = 0; k < M; k++) { for (int i = 0; i < N; i++) { psums[k][i + 1] = psums[k][i] + (arr[i] == k); } vector<int> last_vals(M, 0); for (int i = 0; i < N; i++) { if (arr[i] != k) { last_vals[arr[i]] += psums[k][i]; pref_vals[k][i + 1] = last_vals[arr[i]]; } } last_vals.assign(M, 0); for (int i = N - 1; i >= 0; i--) { if (arr[i] != k) { last_vals[arr[i]] += psums[k][N] - psums[k][i]; suff_vals[k][i] = last_vals[arr[i]]; } } // dmpn(k); dmp(suff_vals[k]); } auto func = [&](int i, int j, int mask) { int pref = 0, suff = 0; if (i >= 0) { int pref_cnt = psums[arr[i]][i + 1]; pref = (pref_cnt * (pref_cnt - 1)) / 2; } if (j < N) { int suff_cnt = psums[arr[j]][N] - psums[arr[j]][j]; suff = (suff_cnt * (suff_cnt - 1)) / 2; } for (int k = 0; k < M; k++) if (ith_bit(mask, k)) { if (i >= 0) pref += 2 * pref_vals[k][i + 1]; if (j < N) suff += 2 * suff_vals[k][j]; } return pref + suff; }; vector<int> dp(M2, N * N); dp[0] = 0; for (int mask = 1; mask < M2; mask++) { // print_bits(mask); for (int k = 0; k < M; k++) if (ith_bit(mask, k) == 1) { int pmask = mask ^ (1 << k); int lo = 0, hi = sz(indices[k]) - 1; while (hi - lo > 2) { int mid1 = lo + (hi - lo) / 3; int mid2 = hi - (hi - lo) / 3; int f1 = func(indices[k][mid1], indices[k][mid1 + 1], pmask); int f2 = func(indices[k][mid2], indices[k][mid2 + 1], pmask); if (f1 > f2) lo = mid1; else hi = mid2; } int curr = N * N; for (int mid = lo; mid < hi; mid++) curr = min(curr, func(indices[k][mid], indices[k][mid + 1], pmask)); int val = dp[pmask] + curr; dp[mask] = min(dp[mask], val); } } double ans = (double)dp[M2 - 1] / (double)2; cout << ans << endl; } int32_t main() { ios::sync_with_stdio(false); cout << setprecision(12); cin.tie(0); cout.tie(0); int t = 1; // cin >> t; while (t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...