Submission #134613

#	Time	Username	Problem	Language	Result	Execution time	Memory
134613		Mahdi_Jfri	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	78 ms	5240 KiB

molecules

#include "molecules.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back

const int maxn = 2e5 + 20;

ll sum[maxn];

int w[maxn] , ind[maxn];

bool cmp(int a , int b)
{
	return w[a] < w[b];
}

vector<int> find_subset(int l, int u, vector<int> W)
{
	int n = W.size();
	for(int i = 0; i < n; i++)
		w[i] = W[i] , ind[i] = i;

	sort(ind , ind + n , cmp);
	for(int i = 0; i < n; i++)
		sum[i + 1] = sum[i] + w[ind[i]];

	ll s = 0;
	for(int i = n; i >= 0; i--)
	{
		if(i < n)
			s += w[ind[i]];

		int k = lower_bound(sum , sum + n + 1 , l - s) - sum;
		if(k <= i && sum[k] + s <= u)
		{
			vector<int> ans;
			for(int j = 0; j < k; j++)
				ans.pb(ind[j]);
			for(int j = i; j < n; j++)
				ans.pb(ind[j]);

			return ans;
		}
	}

	vector<int> tmp;
	return tmp;
}

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