Submission #599567

#TimeUsernameProblemLanguageResultExecution timeMemory
599567fvogel499Boarding Passes (BOI22_passes)C++17
0 / 100
2083 ms3464 KiB
/* * File created on 07/19/2022 at 15:24:35. * Link to problem: * Description: * Time complexity: O() * Space complexity: O() * Status: --- * Copyright: Ⓒ 2022 Francois Vogel */ #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define pii pair<int, int> #define f first #define s second #define vi vector<int> #define all(x) x.begin(), x.end() #define size(x) (int)((x).size()) #define pb push_back #define ins insert #define cls clear #define int ll #define ll long long #define ld long double typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; signed main() { cin.tie(0); ios_base::sync_with_stdio(0); cout << fixed << setprecision(3); string b; cin >> b; const int n = size(b); int gK = 0; for (char i : b) if (i-'A'+1 > gK) gK = i-'A'+1; vi toPermute; for (int i = 0; i < gK; i++) toPermute.pb(i); ld offMin = n*n; do { for (int i = 0; i < n; i++) { b[i] = char('A'+toPermute[b[i]-'A']); } ld res = 0; for (int i = 0; i < gK; i++) { vi pos; for (int j = 0; j < n; j++) if (b[j]-'A' == i) { pos.pb(j); } if (pos.empty()) continue; int pref [n]; for (int j = 0; j < n; j++) pref[j] = (b[j]-'A' < i); for (int j = 1; j < n; j++) pref[j] += pref[j-1]; int suf [n]; for (int j = 0; j < n; j++) suf[j] = (b[j]-'A' < i); for (int j = n-2; j >= 0; j--) suf[j] += suf[j+1]; for (int j = 0; j < size(pos); j++) { int dl = 0; if (pos[j]) dl = pref[pos[j]-1]; int dr = 0; if (pos[j]+1 < n) dr = suf[pos[j]+1]; int cl = j; int cr = size(pos)-1-j; ld dp [cl+1][cr+1]; for (int sum = cl+cr; sum >= 0; sum--) { for (int x = 0; x <= cl; x++) { int y = sum-x; if (y < 0 || y > cr) continue; ld tp = cl-x+cr-y+1; dp[x][y] = (ld)(1)/tp*min(dl+x, dr+y); if (x < cl) { dp[x][y] += dp[x+1][y]*(cl-x)/tp; } if (y < cr) { dp[x][y] += dp[x][y+1]*(cr-y)/tp; } } } res += dp[0][0]; } } offMin = min(offMin, res); vi invToPermute(gK); for (int i = 0; i < gK; i++) invToPermute[toPermute[i]] = i; for (int i = 0; i < n; i++) { b[i] = char('A'+invToPermute[b[i]-'A']); } } while (next_permutation(all(toPermute))); cout << offMin; cout.flush(); int d = 0; d++; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...