# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1098975 | 2024-10-10T11:46:22 Z | crafticat | Boarding Passes (BOI22_passes) | C++17 | 3 ms | 2324 KB |
#include <bits/stdc++.h> #include <utility> using ll = long long; using namespace std; #define F0R(i, n) for (ll i= 0; i < n;i++) template<typename T> using V = vector<T>; using vi = V<ll>; using vvi = V<vi>; #define pb push_back using pi = pair<ll, ll>; #define all(x) begin(x), end(x) #define f first #define s second #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; double add(vi x, Tree<int> &points) { long double expected = 0; F0R(i, x.size()) { int orgLEF = points.order_of_key(x[i]); int orgRIG = points.size() - orgLEF; double lef = orgLEF + (i / 2.0); double rig = orgRIG + (x.size() - i - 1) / 2.0; expected += min(lef, rig); } return expected; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); string str; cin >> str; set<int> ind; vvi groups(26); F0R(i, str.size()) { int id = str[i] - 'A'; groups[id].pb(i); ind.insert(id); } vi perm; for (auto x : ind) perm.pb(x); double ans = 1e18; do { Tree<int> points; double expected = 0; for (auto x : perm) { expected += add(groups[x], points); } ans = min(ans, expected); } while (std::next_permutation(all(perm))); cout << fixed << ans; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | found '100800.5000000000', expected '100800.5000000000', error '0.0000000000' |
2 | Correct | 0 ms | 348 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
3 | Correct | 0 ms | 348 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
4 | Correct | 0 ms | 344 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
5 | Correct | 1 ms | 348 KB | found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
6 | Correct | 2 ms | 2068 KB | found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000' |
7 | Correct | 2 ms | 2324 KB | found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000' |
8 | Correct | 2 ms | 2324 KB | found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000' |
9 | Correct | 2 ms | 2324 KB | found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000' |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 | Correct | 1 ms | 348 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 | Incorrect | 3 ms | 424 KB | 1st numbers differ - expected: '1023.0000000000', found: '165.5000000000', error = '0.8382209189' |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 | Correct | 1 ms | 348 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 | Incorrect | 3 ms | 424 KB | 1st numbers differ - expected: '1023.0000000000', found: '165.5000000000', error = '0.8382209189' |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | found '100800.5000000000', expected '100800.5000000000', error '0.0000000000' |
2 | Correct | 0 ms | 348 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
3 | Correct | 0 ms | 348 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
4 | Correct | 0 ms | 344 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
5 | Correct | 1 ms | 348 KB | found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
6 | Correct | 2 ms | 2068 KB | found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000' |
7 | Correct | 2 ms | 2324 KB | found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000' |
8 | Correct | 2 ms | 2324 KB | found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000' |
9 | Correct | 2 ms | 2324 KB | found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000' |
10 | Correct | 1 ms | 348 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
11 | Correct | 1 ms | 348 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
12 | Incorrect | 3 ms | 424 KB | 1st numbers differ - expected: '1023.0000000000', found: '165.5000000000', error = '0.8382209189' |
13 | Halted | 0 ms | 0 KB | - |