Submission #568381

#	Time	Username	Problem	Language	Result	Execution time	Memory
568381		Trisanu_Das	Detecting Molecules (IOI16_molecules)	C++17	9 / 100	1 ms	300 KiB

molecules

#include <bits/stdc++.h>
#include "molecules.h"
using namespace std;
#define ff first
#define ss second
 
vector<int> find_subset(int l, int u, vector<int> w){
  vector<pair<int, int> > w_sort;
  int n = w.size();
  for(int i = 0; i < n; i++) w_sort.push_back({w[i], i});
  sort(w_sort.begin(), w_sort.end());
  int sum = 0;
  vector<int> ans;
  for(int i = 0; i < n; i++){
    sum += w_sort[i].ff;
    ans.push_back(w_sort[i].ss);
    if(l <= sum && sum <= u) return ans;
  }
  ans.clear();
  if(sum > l || w_sort[0].ff > u) return ans;
  int last = 0; sum = 0;
  for(int i = 0; i < n; i++) {
	if(sum + w_sort[i].ff > l) break;
	sum += w_sort[i].ff;
	last = i;
  }
  int len = last + 1; 
  for(int i = last + 1; i < n; i++) {
		sum -= w_sort[i - len].ff;
		sum += w_sort[i].ff;
		if(sum >= l) {
			for(int j = i - len + 1; j <= i; j++) ans.push_back(w_sort[j].ss);
			return ans;
		}
  }
  return ans;
}

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