Submission #995366

#	Time	Username	Problem	Language	Result	Execution time	Memory
995366		asdfgrace	Boarding Passes (BOI22_passes)	C++17	60 / 100	2032 ms	1880 KiB

passes

#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 / 5
• Subtask 2: 25 / 25
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40