oj.uz

Submission #995364

# Submission time Handle Problem Language Result Execution time Memory
995364 2024-06-08T23:22:24 Z asdfgrace Boarding Passes (BOI22_passes) C++17
60 / 100
 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() {
  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<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';
}

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 1 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 5 ms 1236 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 5 ms 1236 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 1492 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 5 ms 1492 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 1 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 1 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 344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 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 0 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 1 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 1 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 344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 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 0 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 0 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 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 0 ms 348 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 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 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 14 ms 348 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 18 ms 528 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 131 ms 348 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 72 ms 344 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 58 ms 536 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 93 ms 520 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 121 ms 552 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 136 ms 344 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 124 ms 348 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 116 ms 348 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 120 ms 600 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 110 ms 548 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 1 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 5 ms 1236 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 5 ms 1236 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 1492 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 5 ms 1492 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 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 1 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 344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 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 0 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 0 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 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 0 ms 348 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 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 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 14 ms 348 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 18 ms 528 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 131 ms 348 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 72 ms 344 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 58 ms 536 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 93 ms 520 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 121 ms 552 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 136 ms 344 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 124 ms 348 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 116 ms 348 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 120 ms 600 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 110 ms 548 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 4 ms 604 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 9 ms 696 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 600 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 1100 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 5 ms 1236 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 5 ms 1492 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 7 ms 1492 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 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 0 ms 344 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 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 344 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 14 ms 556 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 14 ms 344 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 130 ms 348 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 72 ms 348 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 58 ms 532 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 74 ms 524 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 124 ms 344 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 119 ms 540 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 124 ms 344 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 126 ms 544 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 116 ms 348 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 110 ms 552 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2033 ms 1880 KB Time limit exceeded
97 Halted 0 ms 0 KB -