A16150 | Imbalanced Arrays
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
Ntarsis has come up with an array $a$ of $n$ non-negative integers.
Call an array $b$ of $n$ integers imbalanced if it satisfies the following:
- $-n\le b_i\le n$ , $b_i \ne 0$ ,
- there are no two indices $(i, j)$ ( $1 \le i, j \le n$ ) such that $b_i + b_j = 0$ ,
- for each $1 \leq i \leq n$ , there are exactly $a_i$ indices $j$ ( $1 \le j \le n$ ) such that $b_i+b_j>0$ , where $i$ and $j$ are not necessarily distinct.
Given the array $a$ , Ntarsis wants you to construct some imbalanced array. Help him solve this task, or determine it is impossible.
Call an array $b$ of $n$ integers imbalanced if it satisfies the following:
- $-n\le b_i\le n$ , $b_i \ne 0$ ,
- there are no two indices $(i, j)$ ( $1 \le i, j \le n$ ) such that $b_i + b_j = 0$ ,
- for each $1 \leq i \leq n$ , there are exactly $a_i$ indices $j$ ( $1 \le j \le n$ ) such that $b_i+b_j>0$ , where $i$ and $j$ are not necessarily distinct.
Given the array $a$ , Ntarsis wants you to construct some imbalanced array. Help him solve this task, or determine it is impossible.
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $1 \le t \le 10^5$ ). The description of the test cases follows.
The first line of each test case has a single integer $n$ ( $1 \leq n \leq 10^5$ ).
The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $0 \leq a_i \leq n$ ).
It is guaranteed that the sum of $n$ across all test cases does not exceed $10^5$ .
The first line of each test case has a single integer $n$ ( $1 \leq n \leq 10^5$ ).
The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $0 \leq a_i \leq n$ ).
It is guaranteed that the sum of $n$ across all test cases does not exceed $10^5$ .
输出格式
For each test case, output "NO" if there exists no imbalanced array.
Otherwise, output "YES". Then, on the next line, output $n$ integers $b_1, b_2, \ldots, b_n$ where $b_i \neq 0$ for all $1 \leq i \leq n$ — an imbalanced array.
Otherwise, output "YES". Then, on the next line, output $n$ integers $b_1, b_2, \ldots, b_n$ where $b_i \neq 0$ for all $1 \leq i \leq n$ — an imbalanced array.
输入输出样例
输入 #1
5 1 1 4 1 4 3 4 3 0 1 0 4 4 3 2 1 3 1 3 1
输出 #1
YES 1 NO YES -3 1 -2 YES 4 2 -1 -3 YES -1 3 -1
For the first test case, $b = [1]$ is an imbalanced array. This is because for $i = 1$ , there is exactly one $j$ ( $j = 1$ ) where $b_1 + b_j > 0$ .
For the second test case, it can be shown that there exists no imbalanced array.
For the third test case, $a = [0, 1, 0]$ . The array $b = [-3, 1, -2]$ is an imbalanced array.
- For $i = 1$ and $i = 3$ , there exists no index $j$ such that $b_i + b_j > 0$ .
- For $i = 2$ , there is only one index $j = 2$ such that $b_i + b_j > 0$ ( $b_2 + b_2 = 1 + 1 = 2$ ).
Another possible output for the third test case could be $b = [-2, 1, -3]$ .
For the second test case, it can be shown that there exists no imbalanced array.
For the third test case, $a = [0, 1, 0]$ . The array $b = [-3, 1, -2]$ is an imbalanced array.
- For $i = 1$ and $i = 3$ , there exists no index $j$ such that $b_i + b_j > 0$ .
- For $i = 2$ , there is only one index $j = 2$ such that $b_i + b_j > 0$ ( $b_2 + b_2 = 1 + 1 = 2$ ).
Another possible output for the third test case could be $b = [-2, 1, -3]$ .
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted