Submission #57832

#	Time	Username	Problem	Language	Result	Execution time	Memory
57832		robert	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	106 ms	31836 KiB

molecules

#include <iostream>
#include <vector>
#include <algorithm>
#include "molecules.h"

using namespace std;

vector<int> find_subset(int l, int u, vector<int> wt){
	vector<pair<int, int> > w;
	for(int z=0; z<wt.size(); z++)
		w.push_back({wt[z], z});
	sort(w.begin(), w.end());
	vector<int> res;
	long long sum = 0;
	int x = 0;
	for(; x<w.size(); x++){
		sum += w[x].first;
		if(sum>=l)
			break;
	}
//	cout << sum << endl;
	if(sum<l)
		return res;
	if(sum<=u){
		//solution 0...x
		for(int z=0; z<=x; z++){
			res.push_back(w[z].second);
		}
		return res;
	}
	int y = 0; sum -= w[x].first;
	while(x<w.size()){
		if(sum>=l&&sum<=u)
			break;
		sum -= w[y++].first;
		sum += w[x++].first;
		if(sum>=l&&sum<=u)
			break;
	}
	if(sum<l)
		return res;
	for(int z=y; z<x; z++){
		res.push_back(w[z].second);
	}
	return res;
}
/*
int main(){
	vector<int> r = {15, 17, 16, 18};
	vector<int> a = find_subset(10, 20, r);
	for(int x=0; x<a.size(); x++)
		cout << a[x] << endl;
}*/

Compilation message (stderr)

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

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