/ Vijos / 题库 /

sk抓螃蟹

sk抓螃蟹

背景

sk,zdq想在hzy生日之际送hzy几只螃蟹吃。。。

描述

现有n只螃蟹,每个在一个二维作标上,保证没有任何两个螃蟹重合。sk伸手抓螃蟹了,他怕螃蟹的攻击,当他捉一只螃蟹时,其他螃蟹都朝这只运动(左边的向右,右边的向左,x作标相同的不动)。当然,螃蟹只会在x方向上横行,每秒一单位长度。sk捉一只螃蟹一秒钟,当本秒末若某一只螃蟹与msk的手同x作标,sk的行动失败。问:怎样做才能抓完n只螃蟹?

格式

输入格式

输入
第一行:n。
第二行有2*n正整数,相邻两个用一空格分开,第2*i-1和第2*i个数表示编号为i的螃蟹的x,y作标。输入保证按先x后y的递增序排列。

输出格式

输出:
一共n行,每行一个螃蟹编号,表示sk取螃蟹的先后序列。如有多解,输出第一个编号最小的,如果第一个编号相同,输出第二个编号最大的,再相同,输出第三个编号最小的......

样例1

样例输入1

2
1 3 4 2

样例输出1

1
2

样例2

样例输入2

1
10 5

样例输出2

1

限制

每个测试点一秒

提示

hint
输入数据保证有解...
n<=5000.
0<=所有作标<=2^31-1
本题很简单

信息

ID
1290
难度
2
分类
贪心 | 其他 | 数学 点击显示
标签
(无)
递交数
1088
已通过
662
通过率
61%
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

hzy生日模拟赛