罪犯列队 (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

数据范围与提示

下发文件中本题目录里存在 checker.cpp ，选手可以使用 g++ checker.cpp -o checker -std=c++14 -O2 编译后在 checker的目录下调用 checker [input file] [output file] 或 ./checker [input file] [output file] （视操 作系统而定）来对自己的输出进行检查。注意若输出不符合格式则不保证其能成功运行。

down