ACAC 题库 ac.isam.top
GitHub
AtCoder Regular Contest 227
B
各就各位
Know Your Place
AtCoder
⌀ 1043
原题
← AC →

各就各位AI (CI翻译)

Problem Statement

题目描述

AI (CI翻译)

You are given a length-$N$ sequence of non-negative integers $A=(A_1,A_2,\ldots,A_N)$.

给定一个长度为 $N$ 的非负整数序列 $A=(A_1,A_2,\ldots,A_N)$。AI (CI翻译)

Determine whether there exists a sequence $B=(B_1,B_2,\ldots,B_N)$ that is a permutation of $A$ that satisfies the following condition for every $i=1,2,\ldots,N$, and construct one such sequence if it exists.

请判断是否存在一个序列 $B=(B_1,B_2,\ldots,B_N)$，使得 $B$ 是 $A$ 的一个排列，并且对于每个 $i=1,2,\ldots,N$ 都满足以下条件；如果存在，请构造出这样的一个序列。AI (CI翻译)

  • $B_i$ is equal to the number of integers $j$ satisfying $1 \le j < i$ and $B_j < B_i$.
  • $B_i$ 等于满足 $1 \le j < i$ 且 $B_j < B_i$ 的整数 $j$ 的个数。
AI (CI翻译)

Constraints

约束条件

AI (CI翻译)
  • $1 \le N \le 5 \times 10^5$
  • $0 \le A_i < N$
  • All input values are integers.
  • $1 \le N \le 5 \times 10^5$
  • $0 \le A_i < N$
  • 所有输入值均为整数。
AI (CI翻译)

Input

输入格式

AI (CI翻译)

The input is given from Standard Input in the following format:

输入从标准输入按以下格式给出：AI (CI翻译)

N
A_1 A_2 \ldots A_N

N
A_1 A_2 \ldots A_N
AI (CI翻译)

Output

输出格式

AI (CI翻译)

If there is no sequence $B$ satisfying the condition, output No.

如果不存在满足条件的序列 $B$，输出 No。AI (CI翻译)

If one exists, output Yes and a sequence $B$ in the following format:

如果存在，则按以下格式输出 Yes 以及一个序列 $B`：AI (CI翻译)

Yes
B_1 B_2 \ldots B_N

Yes
B_1 B_2 \ldots B_N
AI (CI翻译)

If multiple sequences satisfy the condition, you may output any of them.

如果有多个满足条件的序列，可以输出其中任意一个。AI (CI翻译)

样例

Input #1
4
3 0 1 0
Output #1
Yes
0 1 0 3
The output sequence is a permutation of $A$. For $i=1,2,3,4$, the number of elements to the left of $B_i$ that are smaller than $B_i$ is $0,1,0,3$, respectively, which equals $B_i$.
Input #2
3
0 2 2
Output #2
No
Since there is only one element smaller than the value $2$, no permutation satisfies the condition.
Input #3
7
4 1 6 0 4 3 1
Output #3
Yes
0 1 1 3 4 4 6
The output sequence is a permutation of $A$. For $i=1,2,\ldots,7$, the number of elements to the left of $B_i$ that are smaller than $B_i$ is $0,1,1,3,4,4,6$, respectively, which equals $B_i$.
题目信息
题号
arc227_b
所属比赛
AtCoder Regular Contest 227
时间限制
2 s
内存限制
1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。