Submission #380733

#	Time	Username	Problem	Language	Result	Execution time	Memory
380733		madlogic	Detecting Molecules (IOI16_molecules)	C++17	69 / 100	144 ms	1132 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) {
  srand(time(NULL));
  int n = (int) w.size();
  vector<bool> dp(u + 1);
  dp[0] = true;
  const int mxxx = 10000;
  if (n <= mxxx && u <= mxxx) {
    vector<int> par(u + 1);
    vector<int> idx(u + 1);
    for (int i = 0; i < n; i++) {
      auto ndp = dp;
      for (int j = w[i]; j <= u; j++) {
        if (!dp[j] && dp[j - w[i]]) {
          ndp[j] = true;
          idx[j] = i;
          par[j] = j - w[i];
        }
      }
      dp = ndp;
    }
    vector<int> res;
    for (int i = l; i <= u; i++) {
      if (dp[i]) {
        while (par[i]) {
          res.push_back(idx[i]);
          i = par[i];
        }
        res.push_back(idx[i]);
        break;
      }
    }
    return res;
  } else {
    vector<pair<int, int>> nums;
    for (int i = 0; i < n; i++) {
      if (w[i] <= u) {
        nums.emplace_back(w[i], i);
      }
    }
    for (int i = 0; i < 2; i++) {
      if (i == 0)
        sort(begin(nums), end(nums));
      else if (i == 1)
        sort(rbegin(nums), rend(nums));
      else
        random_shuffle(begin(nums), end(nums));
      long long cur = 0;
      multiset<pair<long long, int>> ms;
      for (auto& [x, y] : nums) {
        cur += x;
        ms.insert({x, y});
        while (!ms.empty() && cur > u) {
          long long remove = cur - u;
          auto lb = ms.lower_bound({remove, -1});
          if (lb == ms.end()) {
            break;
          }
          cur -= ((*lb).first);
          ms.erase(lb);
        }
      }
      if (cur >= l && cur <= u) {
        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: 15 / 15
• Subtask 5: 23 / 23
• Subtask 6: 0 / 31