제출 #995361

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
995361		asdfgrace	Boarding Passes (BOI22_passes)	C++17	60 / 100	401 ms	1048576 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() {
  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';
}

컴파일 시 표준 에러 (stderr) 메시지

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