#include "molecules_c.h"
#include <string.h>
#define N 200000
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int ww[N];
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k)
if (ww[ii[j]] == ww[i_])
j++;
else if (ww[ii[j]] < ww[i_]) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
sort(ii, l, i);
l = k;
}
}
int find_subset(int lower, int upper, int *ww_, int n, int *res) {
static int ii[N];
int m, h, i;
long long lower_, upper_;
memcpy(ww, ww_, n * sizeof *ww_);
for (i = 0; i < n; i++)
ii[i] = i;
sort(ii, 0, n);
lower_ = upper_ = 0;
for (m = 1; m <= n; m++) {
lower_ += ww[ii[m - 1]], upper_ += ww[ii[n - m]];
if (lower_ <= upper && upper_ >= lower) {
long long sum;
sum = 0;
for (h = 0; h < m; h++)
res[h] = ii[h], sum += ww[ii[h]];
for (h = m - 1; h >= 0 && sum < lower; h--)
res[h] = ii[n - 1 - (m - 1 - h)], sum += ww[res[h]] - ww[ii[h]];
return m;
}
}
return 0;
}
