#include "molecules.h"
#include <vector>
#include <algorithm>
#define MAXN 200005
int n;
std::vector<int> answer;
bool choice[MAXN];
std::pair<int, int> vals[MAXN];
int rev[MAXN];
void make()
{
for(int i = 0; i < n; i++)
if(choice[i])
answer.push_back(rev[i]);
}
std::vector<int> find_subset(int l, int u, std::vector<int> w)
{
n = w.size();
for(int i = 0; i < n; i++)
{
vals[i].first = w[i];
vals[i].second = i;
choice[i] = false;
}
std::sort(vals, vals+n);
for(int i = 0; i < n; i++)
{
w[i] = vals[i].first;
rev[i] = vals[i].second;
}
int cur = 0;
int low = 0; int high = 0;
bool poss = false;
for(int i = 0; i < n; i++)
{
low += w[i];
high += w[n-1-i];
cur += w[n-1-i];
choice[n-1-i] = true;
if(high >= l && low <= u)
{
poss = true;
break;
}
}
if(!poss)
return answer;
if(cur <= u)
{
make();
return answer;
}
int x = 0; int y = n-1;
while(x < n)
{
if(choice[x])
{
x++;
continue;
}
if(!choice[y])
{
y--;
continue;
}
choice[x] = true;
choice[y] = false;
cur += w[x] - w[y];
if(cur <= u)
{
make();
return answer;
}
}
std::abort();
return answer;
}
