CF1348F.Phoenix and Memory
省选/NOI-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Phoenix is trying to take a photo of his n friends with labels 1,2,…,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 i-th friend from the left had a label between ai and bi inclusive. Does there exist a unique way to order his friends based of his memory?
凤凰正试图为他的 n 位朋友(编号为 1,2,…,n)拍照,这些朋友原本按某种特定顺序排成一列。但就在他拍照前,朋友们被一只鸭子吸引而打乱了队形。
现在,凤凰必须恢复原来的顺序,但他记不太清了!他只记得:从左往右数第 i 位朋友的编号在 ai 和 bi 之间(含端点)。根据他的记忆,是否存在唯一一种方式来排列他的朋友们?
输入格式
The first line contains one integer n (1≤n≤2⋅105) — the number of friends.
The i-th of the next n lines contain two integers ai and bi (1≤ai≤bi≤n) — Phoenix's memory of the i-th position from the left.
It is guaranteed that Phoenix's memory is valid so there is at least one valid ordering.
第一行包含一个整数 n(1≤n≤2⋅105)——朋友的数量。
接下来的 n 行中,第 i 行包含两个整数 ai 和 bi(1≤ai≤bi≤n)——凤凰对从左起第 i 个位置的记忆。
保证凤凰的记忆是有效的,即至少存在一种合法的排列。
输出格式
If Phoenix can reorder his friends in a unique order, print YES followed by n integers — the i-th integer should be the label of the i-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,然后输出 n 个整数——第 i 个整数应为从左往右数第 i 个朋友的编号。
否则,输出 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测评打分。不知道怎么写?