# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
995366 | 2024-06-08T23:25:58 Z | asdfgrace | Boarding Passes (BOI22_passes) | C++17 | 2000 ms | 1880 KB |
#include <bits/stdc++.h> using namespace std; #define dbg(x) //x #define prt(x) dbg(cerr << x) #define pv(x) prt(#x << " = " << x << '\n') #define parr(x) dbg(prt(#x << " = "); for (auto y : x) prt(y << ' '); prt('\n')); #define parr2d(x) dbg(prt(#x << " = \n"); for (auto y : x) {parr(y)}; prt('\n')); /* minimize the ev of passes by telling front/back consider each group individually + the impact of prev grps note that in grps, you can basically consider it as a permutation of (sz) nums like a single array when you make each person board, if you know order, start from the end that minimizes passes how do you select a strat that does so? given these have alr boarded probably find contrib for each indiv x before in prev groups, y after and there are j before it and s[i] - j - 1 after it in this grp from front: x + (j(j-1)/2)(j-1!)/(j!) = x + (j-1)/2 from back: x + (s[i]-j-1-1)/2 oh wait you get to choose order of boarding groups!? except we can probably bitmask over the groups or smth and determine ev of impacts within groups themselves? and also we need to be able to find x basic sol = maintain a fenw tree for each bitmask or smth */ int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(3); string s; cin >> s; int n = (int) s.length(); vector<vector<int>> at(15); for (int i = 0; i < n; i++) { at[s[i] - 'A'].push_back(i); } parr2d(at); sort(at.begin(), at.end(), [&] (vector<int> x, vector<int> y) { return x.size() > y.size(); }); while (at.back().empty()) at.pop_back(); reverse(at.begin(), at.end()); parr2d(at); int g = (int) at.size(); vector<int> fenw(n + 1, 0); int cnt = 0; vector<double> cost(1 << g, 1e18); function<int(int)> quer = [&] (int k) { int ret = 0; for (int i = k + 1; i > 0; i -= (i & (-i))) { ret += fenw[i]; } return ret; }; function<void(int, int)> upd = [&] (int k, int val) { for (int i = k + 1; i <= n; i += (i & (-i))) { fenw[i] += val; } }; cost[0] = 0; for (int mask = 0; mask < (1 << g); mask++) { pv(mask); if (mask > 0) { int x = (mask ^ (mask - 1)); for (int bit = 0; bit < g; bit++) { if ((x & (1 << bit))) { if ((mask & (1 << bit))) { for (auto j : at[bit]) { upd(j, 1); } cnt += (int) at[bit].size(); } else { for (auto j : at[bit]) { upd(j, -1); } cnt -= (int) at[bit].size(); } } } } for (int bit = 0; bit < g; bit++) { if (!(mask & (1 << bit))) { double c = cost[mask]; for (int j = 0; j < (int) at[bit].size(); j++) { double lcost = double(quer(at[bit][j] - 1)) + double(double(j) / 2.0); double rcost = double(cnt) - double(quer(at[bit][j])) + double(double((int) at[bit].size() - j - 1) / 2.0); pv(lcost); pv(rcost); c += min(lcost, rcost); pv(c); } cost[mask + (1 << bit)] = min(cost[mask + (1 << bit)], c); } } } cout << cost[(1 << g) - 1] << '\n'; }
# | 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 | 348 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
5 | Correct | 0 ms | 348 KB | found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
6 | Correct | 3 ms | 1308 KB | found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000' |
7 | Correct | 3 ms | 1308 KB | found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000' |
8 | Correct | 4 ms | 1560 KB | found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000' |
9 | Correct | 4 ms | 1560 KB | found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000' |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 | Correct | 1 ms | 344 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 | Correct | 0 ms | 348 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
4 | Correct | 0 ms | 348 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
5 | Correct | 1 ms | 344 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
6 | Correct | 1 ms | 344 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
7 | Correct | 0 ms | 348 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
8 | Correct | 0 ms | 348 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
9 | Correct | 0 ms | 348 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
10 | Correct | 0 ms | 348 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
11 | Correct | 0 ms | 348 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
12 | Correct | 0 ms | 348 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
13 | Correct | 0 ms | 344 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
14 | Correct | 0 ms | 348 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
15 | Correct | 0 ms | 348 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
16 | Correct | 0 ms | 344 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
17 | Correct | 1 ms | 344 KB | found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 | Correct | 1 ms | 344 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 | Correct | 0 ms | 348 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
4 | Correct | 0 ms | 348 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
5 | Correct | 1 ms | 344 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
6 | Correct | 1 ms | 344 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
7 | Correct | 0 ms | 348 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
8 | Correct | 0 ms | 348 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
9 | Correct | 0 ms | 348 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
10 | Correct | 0 ms | 348 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
11 | Correct | 0 ms | 348 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
12 | Correct | 0 ms | 348 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
13 | Correct | 0 ms | 344 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
14 | Correct | 0 ms | 348 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
15 | Correct | 0 ms | 348 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
16 | Correct | 0 ms | 344 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
17 | Correct | 1 ms | 344 KB | found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
18 | Correct | 0 ms | 348 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
19 | Correct | 0 ms | 348 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
20 | Correct | 0 ms | 348 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
21 | Correct | 1 ms | 348 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
22 | Correct | 0 ms | 348 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
23 | Correct | 0 ms | 348 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
24 | Correct | 1 ms | 344 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
25 | Correct | 0 ms | 348 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
26 | Correct | 0 ms | 348 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
27 | Correct | 0 ms | 348 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
28 | Correct | 0 ms | 348 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
29 | Correct | 0 ms | 348 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
30 | Correct | 1 ms | 348 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
31 | Correct | 1 ms | 348 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
32 | Correct | 0 ms | 348 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
33 | Correct | 0 ms | 348 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
34 | Correct | 0 ms | 348 KB | found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
35 | Correct | 1 ms | 348 KB | found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000' |
36 | Correct | 1 ms | 348 KB | found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000' |
37 | Correct | 129 ms | 348 KB | found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000' |
38 | Correct | 70 ms | 344 KB | found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000' |
39 | Correct | 56 ms | 348 KB | found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000' |
40 | Correct | 70 ms | 552 KB | found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000' |
41 | Correct | 119 ms | 348 KB | found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000' |
42 | Correct | 107 ms | 344 KB | found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000' |
43 | Correct | 111 ms | 348 KB | found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000' |
44 | Correct | 105 ms | 344 KB | found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000' |
45 | Correct | 110 ms | 344 KB | found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000' |
46 | Correct | 115 ms | 576 KB | found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000' |
# | 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 | 348 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
5 | Correct | 0 ms | 348 KB | found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
6 | Correct | 3 ms | 1308 KB | found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000' |
7 | Correct | 3 ms | 1308 KB | found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000' |
8 | Correct | 4 ms | 1560 KB | found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000' |
9 | Correct | 4 ms | 1560 KB | found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000' |
10 | Correct | 0 ms | 348 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
11 | Correct | 1 ms | 344 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
12 | Correct | 0 ms | 348 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
13 | Correct | 0 ms | 348 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
14 | Correct | 1 ms | 344 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
15 | Correct | 1 ms | 344 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
16 | Correct | 0 ms | 348 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
17 | Correct | 0 ms | 348 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
18 | Correct | 0 ms | 348 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
19 | Correct | 0 ms | 348 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
20 | Correct | 0 ms | 348 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
21 | Correct | 0 ms | 348 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
22 | Correct | 0 ms | 344 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
23 | Correct | 0 ms | 348 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
24 | Correct | 0 ms | 348 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
25 | Correct | 0 ms | 344 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
26 | Correct | 1 ms | 344 KB | found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
27 | Correct | 0 ms | 348 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
28 | Correct | 0 ms | 348 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
29 | Correct | 0 ms | 348 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
30 | Correct | 1 ms | 348 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
31 | Correct | 0 ms | 348 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
32 | Correct | 0 ms | 348 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
33 | Correct | 1 ms | 344 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
34 | Correct | 0 ms | 348 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
35 | Correct | 0 ms | 348 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
36 | Correct | 0 ms | 348 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
37 | Correct | 0 ms | 348 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
38 | Correct | 0 ms | 348 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
39 | Correct | 1 ms | 348 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
40 | Correct | 1 ms | 348 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
41 | Correct | 0 ms | 348 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
42 | Correct | 0 ms | 348 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
43 | Correct | 0 ms | 348 KB | found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
44 | Correct | 1 ms | 348 KB | found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000' |
45 | Correct | 1 ms | 348 KB | found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000' |
46 | Correct | 129 ms | 348 KB | found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000' |
47 | Correct | 70 ms | 344 KB | found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000' |
48 | Correct | 56 ms | 348 KB | found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000' |
49 | Correct | 70 ms | 552 KB | found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000' |
50 | Correct | 119 ms | 348 KB | found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000' |
51 | Correct | 107 ms | 344 KB | found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000' |
52 | Correct | 111 ms | 348 KB | found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000' |
53 | Correct | 105 ms | 344 KB | found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000' |
54 | Correct | 110 ms | 344 KB | found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000' |
55 | Correct | 115 ms | 576 KB | found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000' |
56 | Correct | 0 ms | 600 KB | found '7.5000000000', expected '7.5000000000', error '0.0000000000' |
57 | Correct | 7 ms | 856 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
58 | Correct | 0 ms | 348 KB | found '100800.5000000000', expected '100800.5000000000', error '0.0000000000' |
59 | Correct | 0 ms | 348 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
60 | Correct | 0 ms | 348 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
61 | Correct | 0 ms | 348 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
62 | Correct | 0 ms | 348 KB | found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
63 | Correct | 5 ms | 1304 KB | found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000' |
64 | Correct | 3 ms | 1308 KB | found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000' |
65 | Correct | 3 ms | 1560 KB | found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000' |
66 | Correct | 4 ms | 1560 KB | found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000' |
67 | Correct | 0 ms | 348 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
68 | Correct | 0 ms | 348 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
69 | Correct | 0 ms | 348 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
70 | Correct | 0 ms | 348 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
71 | Correct | 0 ms | 348 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
72 | Correct | 0 ms | 348 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
73 | Correct | 1 ms | 344 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
74 | Correct | 0 ms | 348 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
75 | Correct | 0 ms | 348 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
76 | Correct | 0 ms | 348 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
77 | Correct | 0 ms | 348 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
78 | Correct | 0 ms | 348 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
79 | Correct | 1 ms | 348 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
80 | Correct | 0 ms | 348 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
81 | Correct | 0 ms | 348 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
82 | Correct | 0 ms | 348 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
83 | Correct | 0 ms | 348 KB | found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
84 | Correct | 0 ms | 348 KB | found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000' |
85 | Correct | 1 ms | 348 KB | found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000' |
86 | Correct | 129 ms | 572 KB | found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000' |
87 | Correct | 72 ms | 600 KB | found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000' |
88 | Correct | 59 ms | 348 KB | found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000' |
89 | Correct | 71 ms | 344 KB | found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000' |
90 | Correct | 111 ms | 344 KB | found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000' |
91 | Correct | 101 ms | 348 KB | found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000' |
92 | Correct | 113 ms | 592 KB | found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000' |
93 | Correct | 105 ms | 348 KB | found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000' |
94 | Correct | 109 ms | 572 KB | found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000' |
95 | Correct | 100 ms | 348 KB | found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000' |
96 | Execution timed out | 2032 ms | 1880 KB | Time limit exceeded |
97 | Halted | 0 ms | 0 KB | - |