AT_abc354_c [ABC354C] AtCoder Magics

题目描述

高桥君拥有 $N$ 张“ AtCoder Magics ”卡牌。我们将第 $i$ 张卡牌称为卡牌 $i$。每张卡牌都有强度和代价两个参数，第 $i$ 张卡牌的强度为 $A_i$，代价为 $C_i$。

高桥君觉得弱的卡牌没用，打算把它们扔掉。具体地，他会不断重复以下操作，直到无法继续为止：

• 选择两张卡牌 $x$ 和 $y$，满足 $A_x > A_y$ 且 $C_x < C_y$，然后把卡牌 $y$ 扔掉。

可以证明，当无法继续操作时，剩下的卡牌集合是唯一确定的。请你求出这些最终未被扔掉的卡牌。

输入格式

输入按以下格式从标准输入读入。

$N$
$A_1$ $C_1$
$A_2$ $C_2$
$\vdots$
$A_N$ $C_N$

输出格式

假设最终未被扔掉的卡牌有 $m$ 张，且它们的编号按升序为 $i_1, i_2, \dots, i_m$，请按以下格式输出：

$m$ $i_1$ $i_2$ $\cdots$ $i_m$

输入输出样例 #1

输入 #1

3
2 4
1 1
3 2

输出 #1

2
2 3

输入输出样例 #2

输入 #2

5
1 1
10 2
100 3
1000 4
10000 5

输出 #2

5
1 2 3 4 5

输入输出样例 #3

输入 #3

6
32 101
65 78
2 29
46 55
103 130
52 40

输出 #3

4
2 3 5 6

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i, C_i \leq 10^9$
• $A_1, A_2, \dots, A_N$ 均互不相同
• $C_1, C_2, \dots, C_N$ 均互不相同
• 输入均为整数

样例解释 1

关注卡牌 $1$ 和 $3$，因为 $A_1 < A_3$ 且 $C_1 > C_3$，所以可以扔掉卡牌 $1$。此后无法再进行操作。此时剩下卡牌 $2$ 和 $3$，请输出它们。

样例解释 2

在这种情况下，任何卡牌都无法被扔掉。

由 ChatGPT 4.1 翻译