罪犯列队 (criminallineup)
题目描述
监狱里有 $n$ 个罪犯，每个罪犯有 体力值 $h_i$ 和攻击力 $d_i$。
三个罪犯 $(i,j,k)$ 从左至右排在一起时，他们的破坏度为 $h_id_j+h_jd_k+h_kd_i$，记作 $f(i,j,k)$。
由于各种原因，神秘人认为破坏度越高越好。
神秘人认为有序三元组 $(i,j,k)$ 是好的，当且仅当其满足 $f(i,j,k) \ge f(k,j,i)$。
神秘人要试图把 $n$ 个罪犯排成一行，使得对于所有 $x,y,z$ 满足 $x,y,z$ 从左至右排列且 $x$ 与 $y$ 相邻 $y$ 与 $z$ 相邻， $x,y,z$ 是好的。请帮助神秘人完成任务。
输入格式
第一行一个正整数 $n$。
接下来 $n$ 行，每行两个正整数 $h_i,d_i$ ，含义如题面所述。
输出格式
一行 $n$ 个数，从左到右为罪犯的排列顺序。如果没有合法排列，输出 $-1$。
样例
样例输入 1
3
1 5
2 6
3 4样例输出 1
3 2 1样例输入 2
4
2 3
4 4
1 1
3 2样例输出 2
3 2 1 4数据范围与提示
| 子任务编号 | $n \le$ | $1 \le a_i,b_i \le $ | 分值 | 特殊性质 |
|---|---|---|---|---|
| 1 | $9$ | $10$ | 16 | 数据随机生成 |
| 2 | $50$ | $10^3$ | 19 | |
| 3 | $1000$ | $10^3$ | 17 | 数据随机生成 |
| 4 | $1000$ | $10^9$ | 26 | |
| 5 | $5000$ | $10^9$ | 22 |
下发文件中本题目录里存在 checker.cpp ，选手可以使用 g++ checker.cpp -o checker -std=c++14 -O2 编译后在 checker的目录下调用 checker [input file] [output file] 或 ./checker [input file] [output file] （视操 作系统而定）来对自己的输出进行检查。注意若输出不符合格式则不保证其能成功运行。