제출 #380749

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
380749		madlogic	Detecting Molecules (IOI16_molecules)	C++17	69 / 100	145 ms	1260 KiB

molecules

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

long long maximum = numeric_limits<long long>::max();

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
  srand(time(NULL));
  int n = (int) w.size();
  int xx = u, yy = l;
  l = min(xx, yy);
  u = max(xx, yy);
  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<long long, int>> nums;
    for (int i = 0; i < n; i++) {
      if (w[i] <= u) {
        nums.emplace_back(w[i], i);
      }
    }
    sort(begin(nums), end(nums));
    long long cur = 0;
    multiset<pair<long long, int>> ms;
    for (auto& [x, y] : nums) {
      if (cur > maximum - x) {
        continue;
      }
      cur += x;
      ms.insert({x, y});
      assert(cur <= maximum);
      while (!ms.empty() && cur > (long long) u) {
        long long remove = cur - (long long) u;
        pair<long long, int> lb;
        if (ms.lower_bound({remove, -1}) == ms.end())
          lb = *ms.rbegin();
        else 
          lb = *(ms.lower_bound({remove, -1}));
        cur -= lb.first;
        ms.erase(ms.lower_bound({lb.first, lb.second}));
      }
    }
    if (cur >= l && cur <= u) {
      vector<int> res;
      for (auto s : ms) {
        res.push_back(s.second);
      }
      return res;
    } else {
      return {};
    }
  }
  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