Submission #701037

#	Time	Username	Problem	Language	Result	Execution time	Memory
701037		Doncho_Bonboncho	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	62 ms	5508 KiB

molecules

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

typedef long long ll;

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
	
	std::vector<std::pair<int, int>> W;
	for( int i=0 ; i<w.size() ; i++ ) W.push_back({w[i], i});
	std::sort(W.begin(), W.end());

	int ind = 0;
	ll currSum = 0;

	int n = (int)W.size();

	for( int i=0 ; i<n ; i++ ){
		while( ind < n and currSum < l ) currSum += W[ind++].first;
		if( currSum >= l and currSum <= u ){
			std::vector<int> nas;
			for( int j = i ; j < ind ;  j++ ) nas.push_back( W[j].second );
			std::sort( nas.begin(), nas.end() );
			return nas;
		}
		currSum -= W[i].first;
	}
		
	return std::vector<int>() ;
}

Compilation message (stderr)

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