CF4D.Mysterious Present

普及+/提高

通过率:0%

时间限制:1.00s

内存限制:64MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Peter decided to wish happy birthday to his friend from Australia and send him a card. To make his present more mysterious, he decided to make a chain. Chain here is such a sequence of envelopes A = {_a_1,  _a_2,  ...,  a__n}, where the width and the height of the i-th envelope is strictly higher than the width and the height of the (i  -  1)-th envelope respectively. Chain size is the number of envelopes in the chain.

Peter wants to make the chain of the maximum size from the envelopes he has, the chain should be such, that he'll be able to put a card into it. The card fits into the chain if its width and height is lower than the width and the height of the smallest envelope in the chain respectively. It's forbidden to turn the card and the envelopes.

Peter has very many envelopes and very little time, this hard task is entrusted to you.

彼得决定为他在澳大利亚的朋友庆祝生日,并寄给他一张贺卡。为了使礼物更加神秘,他决定制作一条“信封链”。此处的“链”是指一个信封序列 $ A = {a_1, a_2, \dots, a_n} $,其中第 $ i $ 个信封的宽度和高度均严格大于第 $ i-1 $ 个信封的宽度和高度($ i \ge 2 $)。链的长度定义为该链中所含信封的数量。

彼得希望利用他手头现有的信封,构造出长度最大的一条链,且该链必须满足:能将一张贺卡放入其中。贺卡能放入该链,当且仅当其宽度和高度均严格小于该链中最小信封(即第一个信封 $ a_1 $)的宽度和高度。注意:不允许旋转贺卡或任何信封。

彼得拥有的信封数量极多,但时间却极为有限——这项艰巨的任务就交给你来完成了!

输入格式

The first line contains integers n, w, h (1  ≤ n ≤ 5000, 1 ≤ w,  h  ≤ 106) — amount of envelopes Peter has, the card width and height respectively. Then there follow n lines, each of them contains two integer numbers w__i and h__i — width and height of the i-th envelope (1 ≤ w__i,  h__i ≤ 106).

第一行包含整数 nn、ww、hh(1≤n≤50001 \leq n \leq 5000,1≤w,h≤1061 \leq w, h \leq 10^6),分别表示彼得拥有的信封数量、卡片的宽度和高度。接下来有 nn 行,每行包含两个整数 wiw_i 和 hih_i,表示第 ii 个信封的宽度和高度(1≤wi,hi≤1061 \leq w_i, h_i \leq 10^6)。

输出格式

In the first line print the maximum chain size. In the second line print the numbers of the envelopes (separated by space), forming the required chain, starting with the number of the smallest envelope. Remember, please, that the card should fit into the smallest envelope. If the chain of maximum size is not unique, print any of the answers.

If the card does not fit into any of the envelopes, print number 0 in the single line.

第一行输出最大链的长度。
第二行输出构成所需链的信封编号(用空格分隔),从最小信封的编号开始。请注意,卡片必须能放入最小的信封中。若最大长度的链不唯一,则输出任意一个答案即可。

如果卡片无法放入任何一个信封中,则在单独一行输出数字 0。

输入输出样例

  • 输入#1

    2 1 1
    2 2
    2 2

    输出#1

    1
    1
  • 输入#2

    3 3 3
    5 4
    12 11
    9 8

    输出#2

    3
    1 3 2

输入解题思路,AI测评打分。不知道怎么写?

首页