oj.uz

Submission #995366

# Submission time Handle Problem Language Result Execution time Memory
995366 2024-06-08T23:25:58 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() {
  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';
}

Subtask #1
5.0 / 5.0

# 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'

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 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'

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 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'

Subtask #4
0 / 40.0

# 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 -