Submission #380724

#	Time	Username	Problem	Language	Result	Execution time	Memory
380724		madlogic	Detecting Molecules (IOI16_molecules)	C++17	Compilation error	0 ms	0 KiB

molecules

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

std::vector<long long> find_subset(long long l, long long u, std::vector<long long> w) {
  srand(time(NULL));
  long long n = (long long) w.size();
  vector<bool> dp(u + 1);
  dp[0] = true;
  const long long mxxx = 10000;
  if (n <= mxxx && u <= mxxx) {
    vector<long long> par(u + 1);
    vector<long long> idx(u + 1);
    for (long long i = 0; i < n; i++) {
      auto ndp = dp;
      for (long long 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<long long> res;
    for (long long 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, long long>> nums;
    for (long long i = 0; i < n; i++) {
      if (w[i] <= u) {
        nums.emplace_back(w[i], i);
      }
    }
    for (long long i = 0; i < 1000; 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, long long>> ms;
      for (auto& [x, y] : nums) {
        cur += x;
        ms.insert({x, y});
        while (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) {
        return {};
      }
      vector<long long> res;
      for (auto s : ms) {
        res.push_back(s.second);
      }
      return res;
    }
  }
  return {};
}

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

Compilation message (stderr)

/tmp/ccrOfpfb.o: In function `main':
grader.cpp:(.text.startup+0x139): undefined reference to `find_subset(int, int, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status