oj.uz

Submission #995361

# Submission time Handle Problem Language Result Execution time Memory
995361 2024-06-08T23:14:36 Z asdfgrace Boarding Passes (BOI22_passes) C++17
60 / 100
 401 ms 1048576 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() {
  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);
  while (at.back().empty()) {
    at.pop_back();
  }
  parr2d(at);
  int g = (int) at.size();
  vector<vector<int>> dp(1 << g, vector<int>(n + 1, 0));
  vector<double> cost(1 << g, 0);
  vector<int> cnt(1 << g, 0);
  function<int(int, int)> quer = [&] (int pos, int k) {
    int ret = 0;
    for (int i = k + 1; i > 0; i -= (i & (-i))) {
      ret += dp[pos][i];
    }
    return ret;
  };
  function<void(int, int, int)> upd = [&] (int pos, int k, int val) {
    for (int i = k + 1; i <= n; i += (i & (-i))) {
      dp[pos][i] += val;
    }
  };
  for (int mask = 1; mask < (1 << g); mask++) {
    pv(mask);
    cost[mask] = 1e18;
    int mn_at = -1, mn_sz = n + 1;
    for (int bit = 0; bit < g; bit++) {
      if ((mask & (1 << bit))) {
        pv(bit);
        if (at[bit].size() < mn_sz) {
          mn_at = bit;
          mn_sz = at[bit].size();
        }
        double c = cost[mask - (1 << bit)];
        for (int j = 0; j < (int) at[bit].size(); j++) {
          double lcost = double(quer(mask - (1 << bit), at[bit][j] - 1)) + double(double(j) / 2.0);
          double rcost = double(cnt[mask - (1 << bit)]) - double(quer(mask - (1 << bit), 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] = min(cost[mask], c);
      }
    }
    dp[mask] = dp[mask - (1 << mn_at)];
    for (int j = 0; j < mn_sz; j++) {
      upd(mask, at[mn_at][j], 1);
    }
    cnt[mask] = cnt[mask - (1 << mn_at)] + mn_sz;
  }
  cout << cost[(1 << g) - 1] << '\n';
}

Compilation message

passes.cpp: In function 'int main()':
passes.cpp:74:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |         if (at[bit].size() < mn_sz) {
      |             ~~~~~~~~~~~~~~~^~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 344 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 440 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 4 ms 2004 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 5 ms 2292 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 7 ms 2256 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 5 ms 2256 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 348 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 0 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 0 ms 348 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 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 0 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 0 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 348 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 0 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 0 ms 348 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 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 0 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 0 ms 348 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 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 0 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 404 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 600 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 1 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 0 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 0 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 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 22 ms 10332 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 23 ms 10588 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 140 ms 40536 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 94 ms 40540 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 88 ms 40664 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 99 ms 40280 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 148 ms 39772 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 120 ms 39772 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 136 ms 39760 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 146 ms 39828 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 144 ms 39840 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 122 ms 39772 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 344 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 440 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 4 ms 2004 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 5 ms 2292 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 7 ms 2256 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 5 ms 2256 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 0 ms 348 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 0 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 0 ms 348 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 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 0 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 0 ms 348 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 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 0 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 404 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 600 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 1 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 0 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 0 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 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 22 ms 10332 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 23 ms 10588 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 140 ms 40536 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 94 ms 40540 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 88 ms 40664 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 99 ms 40280 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 148 ms 39772 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 120 ms 39772 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 136 ms 39760 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 146 ms 39828 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 144 ms 39840 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 122 ms 39772 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 6 ms 3420 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 10 ms 6072 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 4 ms 2004 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 5 ms 2260 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 5 ms 2308 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 6 ms 2256 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 1 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 436 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 0 ms 348 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 0 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 0 ms 436 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 22 ms 10448 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 22 ms 10568 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 153 ms 40784 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 95 ms 40540 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 88 ms 40536 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 103 ms 40272 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 132 ms 39768 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 144 ms 39840 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 127 ms 39772 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 125 ms 39764 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 133 ms 39772 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 124 ms 39768 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Runtime error 401 ms 1048576 KB Execution killed with signal 9
97 Halted 0 ms 0 KB -