Submission #102103

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

molecules

#include <bits/stdc++.h>
#include "molecules.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) {
	srand(time(0));
	vector<pii> v;
	for(int i = 0; i < w.size(); i ++) {
		v.push_back({w[i], i});
	}
	// random_shuffle(v.begin(), v.end());
	sort(v.begin(), v.end());
	while(clock() / (double) CLOCKS_PER_SEC < 0.89) {
		int p = -1, sum = 0;
		multiset<int> ms;
		for(int i = 0; i < v.size(); i ++) {
			while(sum < l and p + 1 < v.size()) {
				p ++; sum += v[p].F;
				ms.insert(v[p].F);
			}
			if(sum <= u and sum >= l and *--ms.end() - *ms.begin() <= u - l) {
				vector<int> ans;
				for(int j = i; j <= p; j ++) {
					ans.push_back(v[j].S);
				}
				return ans;
			}
			sum -= v[i].F;
			ms.erase(ms.find(v[i].F));
		}
		random_shuffle(v.begin(), v.end());
	}
	return vector<int>();
}
//main () {
//	vector<int> ans = find_subset(15, 17, {6, 8, 8, 7});
//	for(auto it: ans) cout << it << ' '; cout << endl;
//}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:10:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < w.size(); i ++) {
                 ~~^~~~~~~~~~
molecules.cpp:18:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v.size(); i ++) {
                  ~~^~~~~~~~~~
molecules.cpp:19:28: 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: 0 / 31