CF1348F.Phoenix and Memory

省选/NOI-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

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

题目描述

Phoenix is trying to take a photo of his nn friends with labels 1,2,…,n1, 2, \dots, n who are lined up in a row in a special order. But before he can take the photo, his friends get distracted by a duck and mess up their order.

Now, Phoenix must restore the order but he doesn't remember completely! He only remembers that the ii-th friend from the left had a label between aia_i and bib_i inclusive. Does there exist a unique way to order his friends based of his memory?

凤凰正试图为他的 nn 位朋友(编号为 1,2,…,n1, 2, \dots, n)拍照,这些朋友原本按某种特定顺序排成一列。但就在他拍照前,朋友们被一只鸭子吸引而打乱了队形。

现在,凤凰必须恢复原来的顺序,但他记不太清了!他只记得:从左往右数第 ii 位朋友的编号在 aia_i 和 bib_i 之间(含端点)。根据他的记忆,是否存在唯一一种方式来排列他的朋友们?

输入格式

The first line contains one integer nn (1≤n≤2⋅1051 \le n \le 2\cdot10^5) — the number of friends.

The ii-th of the next nn lines contain two integers aia_i and bib_i (1≤ai≤bi≤n1 \le a_i \le b_i \le n) — Phoenix's memory of the ii-th position from the left.

It is guaranteed that Phoenix's memory is valid so there is at least one valid ordering.

第一行包含一个整数 nn(1≤n≤2⋅1051 \le n \le 2\cdot10^5)——朋友的数量。

接下来的 nn 行中,第 ii 行包含两个整数 aia_i 和 bib_i(1≤ai≤bi≤n1 \le a_i \le b_i \le n)——凤凰对从左起第 ii 个位置的记忆。

保证凤凰的记忆是有效的,即至少存在一种合法的排列。

输出格式

If Phoenix can reorder his friends in a unique order, print YES followed by nn integers — the ii-th integer should be the label of the ii-th friend from the left.

Otherwise, print NO. Then, print any two distinct valid orderings on the following two lines. If are multiple solutions, print any.

如果凤凰可以将他的朋友们重新排列成一种唯一的顺序,则输出 YES,然后输出 nn 个整数——第 ii 个整数应为从左往右数第 ii 个朋友的编号。

否则,输出 NO。接着,在接下来的两行中分别输出任意两个不同的合法排列。若存在多种解,输出任意一种即可。

输入输出样例

  • 输入#1

    4
    4 4
    1 3
    2 4
    3 4

    输出#1

    YES
    4 1 2 3
  • 输入#2

    4
    1 3
    2 4
    3 4
    2 3

    输出#2

    NO
    1 3 4 2 
    1 2 4 3

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

首页