Submission #949831

#TimeUsernameProblemLanguageResultExecution timeMemory
949831sysiaBoarding Passes (BOI22_passes)C++17
100 / 100
231 ms91308 KiB
//Sylwia Sapkowska #include <bits/stdc++.h> #pragma GCC optimize("O3", "unroll-loops") using namespace std; void __print(int x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << "'" << x << "'";} void __print(const char *x) {cerr << '"' << x << '"';} void __print(const string &x) {cerr << '"' << x << '"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifdef LOCAL #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif #define int long long typedef pair<int, int> T; const int oo = 1e18, oo2 = 1e9+7, K = 30; const int mod = 998244353; typedef long double ld; void solve(){ string s; cin >> s; int n = (int)s.size(); vector<int>used(K); for (auto c: s) used[c-'A']++; vector<int>scale(K); int G = 0; for (int i = 0; i<K; i++) if (used[i]) scale[i] = G++; debug(G); //grupy [0, G-1] vector<vector<int>>what(G); for (int i = 0; i<n; i++) { what[scale[s[i]-'A']].emplace_back(i); } vector<ld>dp((1<<G), oo); dp[0] = 0; vector left(n, vector<int>(G)), right(n, vector<int>(G)); //dla i-tego indeksu grupa g doklada left[i] elementow z lewej for (int i = 0; i<n; i++){ for (int g = 0; g < G; g++){ if (scale[s[i]-'A'] == g) continue; int t = (int)(lower_bound(what[g].begin(), what[g].end(), i)-what[g].begin()); left[i][g] = t; right[i][g] = (int)what[g].size()-t; } } vector<int>prev(G, -1); vector pref(n, vector<int>(G)), suf(n, vector<int>(G)); vector lewo(n, vector<int>(G)), prawo(n, vector<int>(G)); for (int i = 0; i<n; i++){ int c = scale[s[i]-'A']; if (prev[c] != -1) pref[i] = pref[prev[c]]; //pref[i][g] -> suma po left[j][g] po wszystkich j<=i, ze j jest w tej samej grupie co i for (int g = 0; g < G; g++){ pref[i][g] += left[i][g]; } prev[c] = i; lewo[i] = prev; } prev.assign(G, -1); for (int i = n-1; i>=0; i--){ int c = scale[s[i]-'A']; if (prev[c] != -1) suf[i] = suf[prev[c]]; for (int g = 0; g < G; g++) suf[i][g] += right[i][g]; prev[c] = i; prawo[i] = prev; } //2^{G-1} * G * (GlogN) for (int mask = 0; mask < (1<<G); mask++){ for (int i = 0; i<G; i++){ if (mask&(1<<i)) continue; //dokladam grupe i --> to sie wydarzy 2^{G-1} razy int k = (int)what[i].size(); auto check = [&](int p){ ld L = (ld)p/2.0; ld R = (ld)(k-p-1)/2.0; for (int rep = 0; rep < G; rep++){ if (mask&(1<<rep)){ L += left[what[i][p]][rep]; R += right[what[i][p]][rep]; } } return L <= R; }; auto total = [&](int p) -> ld { //jesli osoba p jest ostatnia osoba ktora idzie z lewej strony, to koszt to? //L = (0 + 1 + .. + p)/2 R = (0 + 1 + ... + (k-(p+1)-1))/2 ld L = (ld)(p*(p+1))/4.0; ld R = (ld)(k-p-2)*(k-p-1)/4.0; for (int rep = 0; rep < G; rep++){ if (mask&(1<<rep)){ if (p >= 0) { L += pref[what[i][p]][rep]; debug(pref[what[i][p]][rep]); } if (p+1 < k){ R += suf[what[i][p+1]][rep]; debug(suf[what[i][p+1]][rep]); } } } return L+R; }; //pewien prefiks przyjdzie z lewej, pewien sufiks z prawej int l = 0, r = k-1, curr = -1; while (r >= l){ int m = (l+r)/2; if (check(m)){ curr = m; l = m+1; } else { r = m-1; } } dp[mask^(1<<i)] = min(dp[mask^(1<<i)], dp[mask] + total(curr)); } } cout << fixed << setprecision(10) << dp.back() << "\n"; } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...