Submission #185395

#	Time	Username	Problem	Language	Result	Execution time	Memory
185395		oofsauce	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	69 ms	8336 KiB

molecules

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

using namespace std;

vector<int> find_subset(int l, int u, vector<int> w) {
  vector<pair<long long,long long>> sorted;

  for(long long i = 0; i < w.size(); i++) {
    sorted.push_back({w[i], i});
  }

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

  long long acc = 0;
  long long b = sorted.size()-1, a = b;
  acc = sorted[b].first;
  while(acc < l) {
    if(a > 0) {
      a -= 1;
    } else {
      return vector<int>(0);
    }
    acc += sorted[a].first;
  }

  while(acc < l || acc > u) {
    if(a > 0) {
      acc -= sorted[b].first;
      a -= 1;
      b -= 1;
      acc += sorted[a].first;
    } else {
      return vector<int>(0);
    }
  }

  vector<int> range;
  for(int i = a; i <= b; i++) {
    range.push_back(sorted[i].second);
  }

  return range;
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:9:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(long long i = 0; i < w.size(); i++) {
                        ~~^~~~~~~~~~

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