제출 #1358086

#제출 시각아이디문제언어결과실행 시간메모리
1358086avighnaCookies (JOI23_cookies)C++20
12 / 100
1095 ms4584 KiB
#pragma GCC optimize("Ofast,unroll-loops")

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  int n, m;
  cin >> n;
  vector<int> a(n);
  for (int &i : a) { cin >> i; }
  cin >> m;
  vector<int> b(m);
  for (int &i : b) { cin >> i; }

  vector<int> type;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < a[i]; ++j) { type.push_back(i); }
  }

  int tot = accumulate(a.begin(), a.end(), 0);
  // let dp[mask] = minimum number of boxes to divide the cookies in mask
  vector<int> dp(1 << tot, inf);
  dp[0] = 0;
  for (int mask = 1; mask < 1 << tot; ++mask) {
    vector<vector<int>> _with_type(n);
    for (int i = 0; i < tot; ++i) {
      if (mask & 1 << i) {
        _with_type[type[i]].push_back(i);
      }
    }
    for (int &s : b) {
      vector<int> box;
      auto with_type = _with_type;
      vector<int> ord(n);
      iota(ord.begin(), ord.end(), 0);
      sort(ord.begin(), ord.end(), [&](int i, int j) { return with_type[i].size() > with_type[j].size(); });
      int nmask = mask, rem = 0;
      for (int &type : ord) {
        if (rem == s || with_type[type].empty()) { break; }
        int idx = with_type[type].back();
        with_type[type].pop_back();
        box.push_back(type);
        nmask ^= 1 << idx;
        rem++;
      }
      if (rem == s) {
        if (1 + dp[nmask] < dp[mask]) {
          dp[mask] = 1 + dp[nmask];
        }
      }
    }
  }

  int mask = (1 << tot) - 1;
  if (dp[mask] == inf) {
    cout << "-1\n";
    return 0;
  }
  cout << dp[mask] << '\n';
  vector<vector<int>> ans;
  while (mask) {
    vector<vector<int>> _with_type(n);
    for (int i = 0; i < tot; ++i) {
      if (mask & 1 << i) {
        _with_type[type[i]].push_back(i);
      }
    }
    for (int &s : b) {
      vector<int> box;
      auto with_type = _with_type;
      vector<int> ord(n);
      iota(ord.begin(), ord.end(), 0);
      sort(ord.begin(), ord.end(), [&](int i, int j) { return with_type[i].size() > with_type[j].size(); });
      int nmask = mask, rem = 0;
      for (int &type : ord) {
        if (rem == s || with_type[type].empty()) { break; }
        int idx = with_type[type].back();
        with_type[type].pop_back();
        box.push_back(type);
        nmask ^= 1 << idx;
        rem++;
      }
      if (rem == s && 1 + dp[nmask] == dp[mask]) {
        ans.push_back(box);
        mask = nmask;
        break;
      }
    }
  }

  for (auto &box : ans) {
    cout << box.size() << ' ';
    for (int &i : box) { cout << i + 1 << ' '; }
    cout << '\n';
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...