Submission #829666

#	Time	Username	Problem	Language	Result	Execution time	Memory
829666		Boas	Detecting Molecules (IOI16_molecules)	C++17	69 / 100	37 ms	6788 KiB

molecules

#include "molecules.h"

using namespace std;
#include <bits/stdc++.h>

#define MAX_N 200001
#define ALL(x) x.begin(), x.end()
#define loop(x, i) for (int i = 0; i < (x); i++)
typedef int64_t in64;
typedef pair<in64, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef set<int> si;

in64 diff(in64 i, in64 l, in64 u)
{
	if (i < l)
		return l - i;
	if (i > u)
		return i - u;
	return 0;
}

vi find_subset(int l, int u, vi w)
{
	in64 alles = accumulate(ALL(w), (in64)0);
	if (alles < l)
		return {};
	if (alles <= u)
	{
		vi ret;
		loop(w.size(), i) ret.push_back(i);
		return ret;
	}
	vii sortedMolecules; // first weight, second real index
	loop(w.size(), i)
	{
		if (w[i] > u)
			continue;
		if (w[i] >= l)
			return {i};
		sortedMolecules.push_back({w[i], i});
	}
	sort(ALL(sortedMolecules));
	int n = sortedMolecules.size();
	int minSum = 0;
	int maxSum = 0;
	vi mols;
	for (int k = 1; k <= n; k++)
	{
		maxSum += sortedMolecules[n - k].first;
		minSum += sortedMolecules[k - 1].first;
		mols.push_back(sortedMolecules[k - 1].second);
		if (maxSum < l)
			continue;
		if (minSum > u)
			break;
		if (minSum >= l)
			return mols;
		if (maxSum <= u)
		{
			mols.resize(k);
			loop(k, j) mols[j] = (sortedMolecules[n - j - 1].second);
			return mols;
		}
		int sum = minSum;
		int startIndex = 0;
		while (sum < l)
		{
			sum -= sortedMolecules[startIndex].first;
			sum += sortedMolecules[k + startIndex].first;
			startIndex++;
			if (startIndex >= n)
				return {};
			if (startIndex + k >= n)
				return {};
		}
		if (sum > u)
			return {};
		vi ret;
		for (int i = 0; i < k; i++)
		{
			ret.push_back(sortedMolecules[i + startIndex].second);
		}
		return ret;
	}
	return {};
}

Compilation message (stderr)

molecules.cpp: In function 'vi find_subset(int, int, vi)':
molecules.cpp:8:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define loop(x, i) for (int i = 0; i < (x); i++)
      |                                      ^
molecules.cpp:32:3: note: in expansion of macro 'loop'
   32 |   loop(w.size(), i) ret.push_back(i);
      |   ^~~~
molecules.cpp:8:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define loop(x, i) for (int i = 0; i < (x); i++)
      |                                      ^
molecules.cpp:36:2: note: in expansion of macro 'loop'
   36 |  loop(w.size(), i)
      |  ^~~~

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 23 / 23
• Subtask 6: 0 / 31