Submission #1050539

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050539		EntityPlantt	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	36 ms	6348 KiB

molecules

#include "molecules.h"
#include <algorithm>
#include <array>
using namespace std;
vector <int> construct(vector <array <int, 2>> &w, int left, int right) {
	vector <int> ret(left + w.size() - right - 1);
	for (int i = 0; i < left; i++) ret[i] = w[i][1];
	for (int i = 0; i < w.size() - right - 1; i++) ret[i + left] = w[i + right + 1][1];
	return ret;
}
vector <int> find_subset(int l, int u, vector <int> _w) {
	vector <array <int, 2>> w;
	for (int i = 0; i < _w.size(); i++) w.push_back({_w[i], i});
	long long sum = 0;
	int n = w.size();
	sort(w.begin(), w.end());
	int left = 0, right = n - 1;
	while (right >= 0 && sum < l) sum += w[right--][0];
	if (sum < l) return {};
	if (sum <= u) return construct(w, 0, right);
	while (sum < l || sum > u) {
		sum += w[left++][0];
		if (left == n) return {};
		while (right < n - 1 && sum > u) sum -= w[++right][0];
	}
	return construct(w, left, right);
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> construct(std::vector<std::array<int, 2> >&, int, int)':
molecules.cpp:8:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |  for (int i = 0; i < w.size() - right - 1; i++) ret[i + left] = w[i + right + 1][1];
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~
molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:13:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  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