开始: 2026-10-10 11:00:00

【集训07】模拟赛1011

结束: 2026-10-11 23:00:00
当前  2026-11-04 11:35:08  类型: IOI  状态: 已经结束 

P4. 魔法卡牌(magics)
描述

你手上有 N 张魔法卡牌,编号 1 \sim N。第 i 张卡牌的**强度**为 A_i,**费用**为 C_i。强度越大表示越强,费用越小表示越划算。

如果存在另一张卡牌 y 满足

A_y > A_x \quad \text{且} \quad C_y < C_x

(即 y 比 x **既强又便宜**),就称卡牌 x 是**多余**的,多余的卡牌会被丢弃。

请你反复丢弃所有多余的卡牌,直到没有卡牌可以再被丢弃为止,问最后剩下哪些卡牌。

> 说明:本题保证任意两张卡牌的 A 互不相同、C 也互不相同,所以"既强又便宜"里不需要考虑并列的情况。


输入

N

A_1 C_1

A_2 C_2

...

A_N C_N


输出

第一行一个整数,表示最后剩下的卡牌张数 m。

第二行 m 个整数,按**编号升序**输出这些卡牌的编号,用空格分隔,行末换行。


样例

输入

3
2 4
1 1
3 2

输出

2
2 3

输入

5
1 1
10 2
100 3
1000 4
10000 5

输出

5
1 2 3 4 5
提示

- 2 \le N \le 2\times 10^5

- 1 \le A_i \le 10^9,1 \le C_i \le 10^9,且保证所有 A_i 两两不同、所有 C_i 两两不同

样例1说明:卡牌 1(强度 2、费用 4)被卡牌 3(强度 3、费用 2)碾压,丢弃。卡牌 2(强度 1、费用 1)没有更便宜的了,保留。卡牌 3 最强,保留。最后剩下编号 2 和 3。

| t1 | 10 | 2 \le N \le 10,A_i, C_i \le 50 |  

| t2 | 20 | N \le 300 |  

| t3 | 30 | N \le 5000 |  

| t4 | 40 | N \le 2\times 10^5; 


提交

题目参数
时间限制 1 秒
内存限制 128 MB
提交