#include <bits/stdc++.h>
#include "molecules.h"
using namespace std;
#define pb push_back
#define pi pair<int,int>
#define ll long long
#define mp make_pair
vector<pi> sorted;
pair<ll, pair<int,int>> eval(int k, int l, int u){
int n = sorted.size();
ll curans = 0;
int left = 0;
int right = left + k;
for(int i =left; i <= right; i++)
curans+=sorted[i].first;
if(curans >=l and curans <= u){
return {curans, {left, right}};
}
if(curans > u){
return {curans, {left, right}};
}
while(curans <l){
if(left >=n)
return {curans, {left, right}};
curans -= sorted[left].first;
left++;
right++;
if(right >= n)
return {curans, {left, right}};
curans += sorted[right].first;
if(curans >= l and curans <= u)
return {curans, {left, right}};
else if(curans >= u )
return {curans, {left, right}};
}
return {curans, {left, right}};
}
vector<int> find_subset(int l, int u, vector<int> w) {
int n = w.size();
sorted.clear();
sorted.resize(n);
for(int i =0;i<n ; i++)
sorted[i] = {w[i], i};
sort(sorted.begin(), sorted.end());
int lpntr = -1, rpntr = -1;
int leftk = 1;
int rightk = n ;
while(leftk <= rightk){
int mid = (leftk + rightk) /2;
pair<ll, pair<int,int>> res = eval(mid, l, u);
if(res.first < l){
leftk = mid + 1;
}
else if( res.first > u){
rightk = mid -1;
}
else{
lpntr = res.second.first;
rpntr = res.second.second;
break;
}
}
if(lpntr == -1 and rpntr == -1)
return vector<int> ();
vector<int> ans;
for(int i = max(0,lpntr); i<= rpntr; i++)
ans.pb(sorted[i].second);
sort(ans.begin(), ans.end());
return ans;
}
/***************/
