Submission #626949

#	Time	Username	Problem	Language	Result	Execution time	Memory
626949		Trunkty	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	96 ms	14940 KiB

molecules

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
//#define ll ll

vector<int> find_subset(int l, int u, vector<int> w){
	vector<vector<ll>> v;
	for(ll i=0;i<w.size();i++){
		v.push_back({w[i],i});
	}
	sort(v.begin(),v.end());
	ll curra=0,currb=0,num=-1;
	for(ll i=0;i<v.size();i++){
		curra += v[i][0];
		currb += v[v.size()-i-1][0];
		if(curra>u){
			return {};
		}
		if(currb>=l){
			num = i;
			break;	
		}
	}
	if(num==-1){
		return {};
	}
	ll curr=curra;
	vector<int> ans;
	if(curr>=l and curr<=u){
		for(ll j=0;j<=num;j++){
			ans.push_back(v[j][1]);
		}
		return ans;
	}
	for(ll i=num;i>=0;i--){
		curr -= v[i][0];
		curr += v[i+v.size()-num-1][0];
		if(curr>=l and curr<=u){
			for(ll j=0;j<i;j++){
				ans.push_back(v[j][1]);
			}
			for(ll j=i;j<=num;j++){
				ans.push_back(v[j+v.size()-num-1][1]);
			}
			break;
		}
	}
	return ans;
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:10:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |  for(ll i=0;i<w.size();i++){
      |             ~^~~~~~~~~
molecules.cpp:15:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  for(ll i=0;i<v.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