#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct comp{
int poz, val;
};
bool rule(comp A, comp B)
{
if (A.val == B.val)
return A.poz < B.poz;
return A.val < B.val;
}
vector<int> find_subset(int l, int u, vector<int> v)
{
int n = v.size();
set<int> Set;
vector<int> result;
vector<comp> w(n);
for (int i = 0; i < n; i++)
{
w[i].val = v[i];
w[i].poz = i;
}
sort(w.begin(), w.end(), rule);
//base conditions
if(u < w[0].val)
return result;
if (u - l < w[n-1].val - w[0].val)
return result;
//closest partial sum to u
ll sum = 0;
int i;
for (i = 0; i < n; i++)
{
if (sum + w[i].val > u)
break;
sum+= w[i].val;
Set.insert(w[i].poz);
}
for (int j = n - 1; j >= i; j--)
{
if (l <= sum && sum <= u)
break;
auto poz = Set.begin();
sum= sum - v[*poz] + w[j].val;
Set.erase(poz);
Set.insert(w[j].poz);
}
//verificare daca ne putem incadra in termeni
if (l <= sum && sum <= u)
{
for (auto p = Set.begin(); p != Set.end(); p++)
{
result.push_back(*p);
Set.erase(p);
}
}
return result;
}
