Responsive image

问题 F: Magics

问题 F: Magics

时间限制: 2 Sec  内存限制: 128 MB
提交: 0  解决: 12
[提交][状态][讨论版][命题人:]

题目描述



小劉有 N 张纸牌,来自纸牌游戏 "Magics"

其中的 i 张卡将被称为 i 张卡。每张卡都有两个参数:强度和成本。

卡片 i 的强度为 A i成本为 Ci

他不喜欢弱牌,所以他会弃掉它们。具体来说,他会重复下面的操作,直到无法再进行为止:选择两张牌 x y ,即 A x>A y C x<C y弃牌 y

可以证明,当无法再进行操作时,剩下的牌的集合是唯一确定的。请找出这组牌。

2<=N<=2e5

1<=Ai,Ci<=1e9
A1,A2,...,An都是不同的

C1,C2,...,Cn都是不同的

所有输入值都是整数

输入描述

N
A1 C1
A2 C2
.
.
.
AN CN


输出描述

m
i1 i2 ....im

样例输入

3
2 4
1 1
3 2

样例输出

2
2 3

提示

集中在纸牌 1和3上,我们有 A1< A3;和 C1>C3;,因此可以弃掉纸牌 1

无法进行进一步的操作。此时还剩下纸牌2和3,因此将它们打印出来。

[提交][状态]
ACM算法攻关部
  • Anything about this OnlineJudge, Please Contact Administrator. Click add QQ

    OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap

    Copyright 2016 ACM算法攻关部
    关于网站改版