A16692 | $Distinct Elements$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定一个数组 $c$，定义 $f(c)$ 为 $c$ 中不同元素的个数。例如，$f([1,2,2])=2$，因为 $[1,2,2]$ 中有两个不同的元素：$1$ 和 $2$。另外，定义 $c[i,j]$ 表示 $c$ 下标从 $i$ 到 $j$ 的子数组（即 $[c_i, c_{i+1}, \ldots, c_j]$）。 现在有一个长度为 $n$ 的数组 $a$。定义长度为 $n$ 的数组 $b$，其中 $b_i = f(a[1,i]) + f(a[2,i]) + \ldots + f(a[i,i])$。现在给定数组 $b$，请你构造任意一个满足 $1 \leq a_i \leq n$ 的数组 $a$。保证至少存在一个可行解。 *补充说明：数组 $x$ 被称为数组 $y$ 的子数组，当且仅当 $x$ 可以通过从 $y$ 的开头和结尾各删除若干（可能为零或全部）元素得到。*

输入包含多组测试数据。第一行是测试用例组数 $t$（$1 \le t \le 10^4$）。接下来是每组测试数据的描述。 每组测试数据的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示 $a$ 和 $b$ 的元素个数。 每组测试数据的第二行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \leq b_i \leq 10^{18}$）。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出任意一个满足条件的 $a$，使得 $1 \leq a_i \leq n$。每组测试数据输出一行。 对于每一个测试用例，保证至少存在一个 $a$ 满足条件。

输入 #1

输出 #1

C++ 编辑器

输入

输出