机器人
题目背景
小 W 购买了一个机器人。
题目描述
现在,小 W 希望机器人去帮他完成 $n$ 个任务。
每个任务有两种属性:完成需要花的钱 $w_i$,成功率 $p_i$。
小 W 需要将任务按一定顺序排序,随后,机器人会按如下方式做任务:
- 从第一个任务开始做;
- 花费代价做完第 $i$ 个任务后,如果成功,则继续做第 $i+1$ 个任务,否则重新从第一个任务开始做;
- 成功做完第 $n$ 个任务后,流程结束。
例如,当 $n=2$ 时,一个可能的流程为:
- 做任务 $1$,失败;
- 做任务 $1$,成功;
- 做任务 $2$,失败;
- 做任务 $1$,成功;
- 做任务 $2$,成功;
- 流程结束,总花费为 $3w_1+2w_2$。
现在,小 W 希望学 OI 的你帮他找到一种排列顺序,使得他的期望花费最小。
输入输出格式
输入格式
第一行一个整数 $n$,表示任务的数量。
接下来一行 $n$ 个整数 $w_1,w_2,\cdots,w_n$,意义如上。
接下来一行 $n$ 个整数 $P_1,P_2,\cdots,P_n$,其中 $P_i=p_i\times10^4$,
$p_i$ 的意义如上。
输出格式
如果无论如何也不可能完成任务,那么输出一行一个字符串`Impossible`。
否则,输出一行 $n$ 个整数 $c_1,c_2,\cdots,c_n$,其为 $1,2,\cdots,n$ 的一个排列,表示任务的安排顺序,安排的第 $i$ 件任务是输入中的第 $c_i$ 件任务。
输入输出样例
输入样例 #1
2
999 1
5000 10000
输出样例 #1
1 2
输入样例 #2
1
1
0
输出样例 #2
Impossible
说明
样例一解释:可以感性理解。既然任务 $2$ 一定成功,那放到最后做肯定不劣。
样例二解释:显然这个任务不可能完成,它的成功率为 $0$。
**注意:无论任务是否成功,总是要花费 $w_i$ 的代价去做。**
********
本题带有 $\text{SPJ}$。如果你的输出与答案的输出一样优(或者都是`Impossible`),那么你将在这个测试点获得满分,否则你将在这个测试点不获得任何分数。
由于某种原因,本题不提供 $\text{SPJ}$ 给选手。
********
数据范围:
对于 $10\%$ 的数据,$1\le n\le 10$。
对于另外 $20\%$ 的数据,所有 $w_i$ 相等。
对于另外 $20\%$ 的数据,所有 $p_i$ 相等。
对于所有数据,$1\le n\le 2\times10^5$,$1\le w_i\le 10^9$,$0\le P_i\le10^4$。