Submission #380743

#	Time	Username	Problem	Language	Result	Execution time	Memory
380743		madlogic	Detecting Molecules (IOI16_molecules)	C11	Compilation error	0 ms	0 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();
  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);
      }
    }
    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;
          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;
      }
    }
  }
  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 << ' ';
//   }
// }

Compilation message (stderr)

In file included from molecules.c:1:
molecules.h:3:10: fatal error: vector: No such file or directory
    3 | #include <vector>
      |          ^~~~~~~~
compilation terminated.