P6169 [IOI 2016] molecules

Peter works at a company that has built a machine to detect molecules. The weight of each molecule is a positive integer. The detection range of the machine is $[l,u]$, where both $l$ and $u$ are positive integers. The machine can detect a set of molecules if and only if this set contains a subset whose total weight lies within the detection range. Consider $n$ molecules with weights $w_0,\cdots,w_{n-1}$. If there exists a set of indices (and all indices in the set are distinct) $I=\{i_1,\cdots,i_m\}$ such that $l\le w_{i_1}+\cdots+w_{i_m}\le u$, then the detection succeeds. Due to the details of the machine, the difference between $l$ and $u$ is guaranteed to be at least the difference between the heaviest and the lightest molecule, i.e. $u-l \ge w_{max}-w_{min}$, where $w_{max}=\max(w_0,\cdots,w_{n-1})$ and $w_{min}=\min(w_0,\cdots,w_{n-1})$. Your task is to write a program that finds a subset whose total weight lies within the detection range, or determines that no such subset exists. ### Sample 1 ``` 4 15 17 6 8 8 7 ``` In this example, we have four molecules with weights $6,8,8$ and $7$. The machine can detect a subset whose total weight is between $15$ and $17$ (including $15$ and $17$). Note that $17-15 \ge 8-6$. The sum of the weights of molecule $1$ and molecule $3$ is $w_1+w_3=8+7=15$, so the output should be ``` 2 1 3 ``` Other possible correct answers are ``` 2 1 2 ``` ($w_1+w_2=8+8=16$) and ``` 2 2 3 ``` ($w_2+w_3=8+7=15$). ### Sample 2 ``` 4 14 15 5 5 6 6 ``` In this example, we have four molecules with weights $5,5,6$ and $6$. We want to find a subset whose total weight is between $14$ and $15$ (including $14$ and $15$). Note that $15-14 \ge 6-5$. Since there is no subset whose total weight is between $14$ and $15$, output `0`.

- The first line: integers $n,l$ and $u$. - The second line: $n$ integers: $w_0,\cdots,w_{n-1}$.

If there is a subset that satisfies the condition: - The first line: output the size of the subset $x$. - The second line: $x$ integers, the indices of the molecules in a valid subset. If not, output `0`.

Constraints: for $100\%$ of the data, $n \le 2 \times 10^5$, $w_i \le 2^{31}-1$, and $l,u \le 2^{31}-1$. Translated by ChatGPT 5