P6024 Robot

Xiao W bought a robot.

Now, Xiao W wants the robot to help him complete $n$ tasks. Each task has two attributes: the money needed to complete it $w_i$, and the success probability $p_i$. Xiao W needs to arrange the tasks in some order. Then, the robot will do the tasks in the following way: - Start from the first task. - After paying the cost to do task $i$, if it succeeds, then continue to do task $i+1$; otherwise, restart from the first task. - After successfully completing task $n$, the process ends. For example, when $n=2$, one possible process is: - Do task $1$, fail. - Do task $1$, succeed. - Do task $2$, fail. - Do task $1$, succeed. - Do task $2$, succeed. - Process ends, and the total cost is $3w_1+2w_2$. Now, Xiao W wants you, who are studying OI, to help him find an ordering that makes his expected cost as small as possible. #

The first line contains an integer $n$, the number of tasks. The next line contains $n$ integers $w_1,w_2,\cdots,w_n$, as described above. The next line contains $n$ integers $P_1,P_2,\cdots,P_n$, where $P_i=p_i\times10^4$, and the meaning of $p_i$ is as described above. #

If it is impossible to complete the tasks no matter what, output one line with the string `Impossible`. Otherwise, output one line with $n$ integers $c_1,c_2,\cdots,c_n$, which is a permutation of $1,2,\cdots,n$. This represents the task order: the $i$-th arranged task is task $c_i$ in the input. #

Explanation for Sample 1: You can understand it intuitively. Since task $2$ is guaranteed to succeed, putting it last is definitely not worse. Explanation for Sample 2: Obviously, this task can never be completed, because its success probability is $0$. **Note: Whether the task succeeds or not, you always have to pay the cost $w_i$ to attempt it.** ******** This problem uses $\text{SPJ}$. If your output is at least as good as the answer output (or both are `Impossible`), then you will get full score on this test point; otherwise, you will get $0$ score on this test point. For some reason, this problem does not provide the $\text{SPJ}$ to contestants. ******** Constraints: For $10\%$ of the testdata, $1\le n\le 10$. For another $20\%$ of the testdata, all $w_i$ are equal. For another $20\%$ of the testdata, all $p_i$ are equal. For all testdata, $1\le n\le 2\times10^5$, $1\le w_i\le 10^9$, $0\le P_i\le10^4$. Translated by ChatGPT 5