Submission #969789

#TimeUsernameProblemLanguageResultExecution timeMemory
969789starchanDetecting Molecules (IOI16_molecules)C++17
100 / 100
44 ms5680 KiB
#include<bits/stdc++.h>
//#include "molecules.h"
using namespace std;
#define ll long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+5
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

vector<int> find_subset(int l, int r, vector<int> W)
{
	int n = W.size(); vector<in> w(n);
	for(int i = 0; i < n; i++)
		w[i] = {W[i], i};
	sort(w.begin(), w.end());
	int k; k = -1;
	ll sl, sr; sl = sr = 0;
	for(int i = 0; i < n; i++)
	{
		sl+=w[i][0]; sr+=w[n-1-i][0];
		if((r >= sl) && (sr >= l))
		{
			k = i+1;
			break;
		}
	}
	vector<int> v; 
	if(k == -1)
		return v;
	vector<bool> vis(k, 1); vis.resize(n);
	int S = sl;
	for(int i = 0; i < min(k, n-k); i++)
	{
		if((l <= S) && (S <= r))
			break;
		vis[n-1-i] = 1; vis[i] = 0;
		S+=(w[n-1-i][0]-w[i][0]);
	}
	if((l <= S) && (S <= r))
	{
		for(int i = 0; i < n; i++)
			if(vis[i])
				v.pb(w[i][1]);
		sort(v.begin(), v.end());
	}
	return v;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...