CF471B.MUH and Important Things
普及-
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
It's time polar bears Menshykov and Uslada from the zoo of St. Petersburg and elephant Horace from the zoo of Kiev got down to business. In total, there are n tasks for the day and each animal should do each of these tasks. For each task, they have evaluated its difficulty. Also animals decided to do the tasks in order of their difficulty. Unfortunately, some tasks can have the same difficulty, so the order in which one can perform the tasks may vary.
Menshykov, Uslada and Horace ask you to deal with this nuisance and come up with individual plans for each of them. The plan is a sequence describing the order in which an animal should do all the n tasks. Besides, each of them wants to have its own unique plan. Therefore three plans must form three different sequences. You are to find the required plans, or otherwise deliver the sad news to them by stating that it is impossible to come up with three distinct plans for the given tasks.
现在,来自圣彼得堡动物园的北极熊 Menshykov 和 Uslada,以及来自基辅动物园的大象 Horace 要开始工作了。当天一共有 n 项任务,每只动物都必须完成所有这些任务。对于每一项任务,它们均已评估其难度。此外,动物们决定按任务难度的顺序来执行任务。遗憾的是,某些任务可能具有相同的难度,因此可执行任务的顺序可能不唯一。
Menshykov、Uslada 和 Horace 请求你解决这一麻烦,为每只动物分别制定一个专属计划。所谓“计划”,即一个序列,描述某只动物应以何种顺序完成全部 n 项任务。此外,每只动物都希望拥有自己独一无二的计划。因此,这三个计划必须构成三个互不相同的序列。你需要找出满足要求的三个计划;若无法为给定的任务构造出三个互不相同的计划,则需向它们传达这个令人遗憾的消息:即该任务集下不存在三个互异的计划。
输入格式
The first line contains integer n (1 ≤ n ≤ 2000) — the number of tasks. The second line contains n integers _h_1, _h_2, ..., h__n (1 ≤ h__i ≤ 2000), where h__i is the difficulty of the i-th task. The larger number h__i is, the more difficult the i-th task is.
第一行包含一个整数 n(1≤n≤2000)——任务的数量。
第二行包含 n 个整数 h1, h2, …, hn(1≤hi≤2000),其中 hi 表示第 i 个任务的难度。数值 hi 越大,表示第 i 个任务越难。
输出格式
In the first line print "YES" (without the quotes), if it is possible to come up with three distinct plans of doing the tasks. Otherwise print in the first line "NO" (without the quotes). If three desired plans do exist, print in the second line n distinct integers that represent the numbers of the tasks in the order they are done according to the first plan. In the third and fourth line print two remaining plans in the same form.
If there are multiple possible answers, you can print any of them.
第一行输出 "YES"(不带引号),表示可以构造出三个互不相同的任务执行方案;否则第一行输出 "NO"(不带引号)。
如果存在所要求的三个方案,则在第二行输出 n 个互不相同的整数,表示第一个方案中任务执行的顺序编号;第三行和第四行以相同格式输出其余两个方案。
若存在多个可能的答案,输出任意一个即可。
输入输出样例
输入#1
4 1 3 3 1
输出#1
YES 1 4 2 3 4 1 2 3 4 1 3 2
输入#2
5 2 4 1 4 8
输出#2
NO
说明/提示
In the first sample the difficulty of the tasks sets one limit: tasks 1 and 4 must be done before tasks 2 and 3. That gives the total of four possible sequences of doing tasks : [1, 4, 2, 3], [4, 1, 2, 3], [1, 4, 3, 2], [4, 1, 3, 2]. You can print any three of them in the answer.
In the second sample there are only two sequences of tasks that meet the conditions — [3, 1, 2, 4, 5] and [3, 1, 4, 2, 5]. Consequently, it is impossible to make three distinct sequences of tasks.
在第一个样例中,任务的难度设置了一个限制:任务 1 和 4 必须在任务 2 和 3 之前完成。这总共给出了四种可能的任务执行顺序:[1, 4, 2, 3]、[4, 1, 2, 3]、[1, 4, 3, 2]、[4, 1, 3, 2]。你可以在答案中输出其中任意三种。
在第二个样例中,仅有两种满足条件的任务序列:[3, 1, 2, 4, 5] 和 [3, 1, 4, 2, 5]。因此,无法构造出三种互不相同的任务序列。
输入解题思路,AI测评打分。不知道怎么写?