Submission #257832

#	Time	Username	Problem	Language	Result	Execution time	Memory
257832		ipaljak	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	62 ms	6252 KiB

molecules

#include "molecules.h"

#include <algorithm>

typedef long long llint;

using namespace std;

vector<int> find_subset(int l, int u, vector<int> w) {
  vector<pair<int, int>> v;
  for (int i = 0; i < (int) w.size(); ++i)
    v.emplace_back(w[i], i);

  sort(v.begin(), v.end());

  int lo = 0, hi = 1;
  llint sum = (llint) v[0].first;
  for (; lo < (int) v.size(); ++lo) {
    while (hi < (int) v.size() && sum < l) sum += (llint) v[hi++].first;
    if (sum >= l && sum <= u) break;
    sum -= (llint) v[lo].first;
  }

  vector<int> ret;
  for (int i = lo; i < hi; ++i)
    ret.push_back(v[i].second);
  return ret;
}

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