Submission #160164

#	Time	Username	Problem	Language	Result	Execution time	Memory
160164		AlexPop28	Detecting Molecules (IOI16_molecules)	C++11	100 / 100	67 ms	3064 KiB

molecules

#include <bits/stdc++.h>
#include "molecules.h"

using namespace std;

vector<int> find_subset(int l, int u, vector<int> w) {
  int n = w.size();
  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int a, int b) {
    return w[a] < w[b];
  });
  int i = 0, j = 0;
  long long sum = 0LL;
  while (i < n && j < n) {
    while (j < n && (i >= j || sum < l)) {
      sum += w[order[j++]];
    }
    while (i + 1 < j && sum > u) {
      sum -= w[order[i++]];
    }
    if (i < j && l <= sum && sum <= u) {
      vector<int> ans;
      for (int p = i; p < j; ++p) {
        ans.emplace_back(order[p]); 
      }
      return ans;
    }
    sum -= w[order[i++]];
  }

  return vector<int>();
}

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