Submission #102734

#	Time	Username	Problem	Language	Result	Execution time	Memory
102734		bert30702	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	69 ms	6224 KiB

molecules

#include <bits/stdc++.h>
#define pii pair<int, int>
#define F first
#define S second
using namespace std;
vector<int> find_subset(int l, int u, vector<int> w) {
	vector<pii> v;
	for(long long i = 0; i < w.size(); i ++) {
		v.push_back({w[i], i});
	}
	sort(v.begin(), v.end());
	long long p = -1, sum = 0;
	for(long long i = 0; i < v.size(); i ++) {
		while(sum < l and p + 1 < v.size()) {
			p ++; sum += v[p].F;
		}
		if(sum <= u and sum >= l and v[p].F - v[i].F <= u - l) {
			vector<int> ans;
			for(long long j = i; j <= p; j ++) {
				ans.push_back(v[j].S);
			}
			return ans;
		}
		sum -= v[i].F;
	}
	return vector<int>();
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:8:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(long long i = 0; i < w.size(); i ++) {
                       ~~^~~~~~~~~~
molecules.cpp:13:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(long long i = 0; i < v.size(); i ++) {
                       ~~^~~~~~~~~~
molecules.cpp:14:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(sum < l and p + 1 < v.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