Submission #1106437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106437		SonicML	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	42 ms	5712 KiB

molecules

#include <vector>
#include <algorithm>

#include "molecules.h"

using namespace std;

int const NMAX = 2e5;
int arr[1 + NMAX];
int ind[1 + NMAX];

bool compareIndex(int a, int b) {
  return (arr[a] < arr[b]);
}

vector <int> find_subset(int l, int u, vector<int> w) {
  vector <int> result;
  int n = w.size();
  for(int i = 0;i < w.size();i++) {
    ind[i] = i;
    arr[i] = w[i];
  }
  sort(ind, ind+n, compareIndex);
  int from = 0;
  long long sum = 0;
  bool foundSol = false;
  for(int to = 0;to < n && !foundSol;to++) {
    sum += arr[ind[to]]; 
    while(sum > u) {
      sum -= arr[ind[from]];
      from++;
    }
    if(l <= sum && sum <= u) {
      foundSol = true;
      for(int i = from;i <= to;i++) {
	result.push_back(ind[i]);
      }
    }
  }
  return result;
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:19:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   for(int 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