Submission #380700

#	Time	Username	Problem	Language	Result	Execution time	Memory
380700		madlogic	Detecting Molecules (IOI16_molecules)	C++17	31 / 100	7 ms	876 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
  int n = (int) w.size();
  vector<vector<int>> dp(u + 1);
  vector<bool> bdp(u + 1);
  bdp[0] = true;
  if (n <= 100 && u <= 1000) {
    for (int i = 0; i < n; i++) {
      auto ndp = dp;
      auto bbdp = bdp;
      for (int j = w[i]; j <= u; j++) {
        if (!bdp[j] && bdp[j - w[i]]) {
          bbdp[j] = true;
          ndp[j] = dp[j - w[i]];
          ndp[j].push_back(i);
        }
      }
      dp = ndp;
      bdp = bbdp;
    }
    for (int i = l; i <= u; i++) {
      if (bdp[i]) {
        return dp[i];
      }
    }
  } else {
    vector<pair<int, int>> nums;
    for (int i = 0; i < n; i++) {
      if (w[i] <= u) {
        nums.emplace_back(w[i], i);
      }
    }
    sort(nums.rbegin(), nums.rend());
    int cur = 0;
    multiset<pair<int, int>> ms;
    for (auto& [x, y] : nums) {
      cur += x;
      ms.insert({x, y});
      while (cur > u) {
        int remove = u - cur;
        auto lb = ms.lower_bound({remove, -1});
        cur -= (*lb).first;
        ms.erase(lb);
      }
    }
    if (cur < l || cur > u) {
      return {};
    }
    vector<int> res;
    for (auto s : ms) {
      res.push_back(s.second);
    }
    return res;
  }
  return {};
}

// int main() {
//   int n, l, r;
//   cin >> n >> l >> r;
//   vector<int> a(n);
//   for (int i = 0; i < n; i++) {
//     cin >> a[i];
//   }
//   for (int p : find_subset(l, r, a)) {
//     cout << p << ' ';
//   }
// }

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 0 / 15
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31