Submission #394385

#	Time	Username	Problem	Language	Result	Execution time	Memory
394385		EncryptingWolf	Detecting Molecules (IOI16_molecules)	C++14	46 / 100	5 ms	600 KiB

molecules

using namespace std;
#include <algorithm>
typedef long long ll;
#include <vector>
#include <iostream>
vector<int> find_subset(int l, int u, vector<int> w)
{
	vector<pair<int,int>> weights;
	for (int i = 0; i < w.size(); i++)
	{
		weights.push_back({ w[i],i });
	}
	sort(weights.begin(), weights.end());
	sort(w.begin(), w.end());
	ll left = 0;
	ll right = 0;
	ll n = w.size();
	vector<int> result(w.size(), 0);
	for (int i = 0; i < n; i++)
	{
		left += w[i];
		right += w[n - i - 1];
		//cout << left << ' ' <<  right << endl;
		if (l <= left && left <= u)
		{
			for (int j = 0; j <= i; j++)
			{
				result[j] = weights[j].second;
			}
			result.resize(i + 1);
			return result;
		}
		else if (l <= right && right <= u)
		{
			for (int j = 0; j <= i; j++)
			{
				//cout << w[n - j - 1];
				result[j] = weights[n-j-1].second;
			}
			result.resize(i + 1);
			return result;
		}
		else if (l > left && u < right)
		{
			long double avg = ((long double) l + u) / 2 / (i+1);
			ll total = 0;
			ll li = 1;
			ll ri = n-1;
			total = w[0];
			result[0] = weights[0].second;
			for (int j = 1; j <= i; j++)
			{
				if ((long double)total / (j) > avg)
				{

					total += w[li];
					result[j] = weights[li].second;
					//cout << li << ' ' << weights[li].second << ' ' << w[li] << endl;
					li++;
				}
				else
				{
					result[j] = weights[ri].second;
					total += w[ri];
					//cout << ri << ' ' << weights[ri].second << ' ' << w[ri] << endl;
					ri--;
				}
			}
			result.resize(i + 1);
			return result;
		}
	}
	return vector<int>(0);
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:9:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |  for (int i = 0; i < w.size(); i++)
      |                  ~~^~~~~~~~~~

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