luogu#P6024. 机器人

机器人

题目背景

小 W 购买了一个机器人。

题目描述

现在,小 W 希望机器人去帮他完成 nn 个任务。

每个任务有两种属性:完成需要花的钱 wiw_i,成功率 pip_i

小 W 需要将任务按一定顺序排序,随后,机器人会按如下方式做任务:

  • 从第一个任务开始做;
  • 花费代价做完第 ii 个任务后,如果成功,则继续做第 i+1i+1 个任务,否则重新从第一个任务开始做;
  • 成功做完第 nn 个任务后,流程结束。

例如,当 n=2n=2 时,一个可能的流程为:

  • 做任务 11,失败;
  • 做任务 11,成功;
  • 做任务 22,失败;
  • 做任务 11,成功;
  • 做任务 22,成功;
  • 流程结束,总花费为 3w1+2w23w_1+2w_2

现在,小 W 希望学 OI 的你帮他找到一种排列顺序,使得他的期望花费最小。

输入格式

第一行一个整数 nn,表示任务的数量。

接下来一行 nn 个整数 w1,w2,,wnw_1,w_2,\cdots,w_n,意义如上。

接下来一行 nn 个整数 P1,P2,,PnP_1,P_2,\cdots,P_n,其中 Pi=pi×104P_i=p_i\times10^4pip_i 的意义如上。

输出格式

如果无论如何也不可能完成任务,那么输出一行一个字符串Impossible

否则,输出一行 nn 个整数 c1,c2,,cnc_1,c_2,\cdots,c_n,其为 1,2,,n1,2,\cdots,n 的一个排列,表示任务的安排顺序,安排的第 ii 件任务是输入中的第 cic_i 件任务。

2
999 1
5000 10000

1 2
1
1
0

Impossible

提示

样例一解释:可以感性理解。既然任务 22 一定成功,那放到最后做肯定不劣。

样例二解释:显然这个任务不可能完成,它的成功率为 00

注意:无论任务是否成功,总是要花费 wiw_i 的代价去做。


本题带有 SPJ\text{SPJ}。如果你的输出与答案的输出一样优(或者都是Impossible),那么你将在这个测试点获得满分,否则你将在这个测试点不获得任何分数。

由于某种原因,本题不提供 SPJ\text{SPJ} 给选手。


数据范围:
对于 10%10\% 的数据,1n101\le n\le 10
对于另外 20%20\% 的数据,所有 wiw_i 相等。
对于另外 20%20\% 的数据,所有 pip_i 相等。
对于所有数据,1n2×1051\le n\le 2\times10^51wi1091\le w_i\le 10^90Pi1040\le P_i\le10^4