CF2147I1.Longest Increasing Path (Easy Version)

这是该问题的简单版本。不同版本之间的区别在于本版本的第二组测试数据为 $n=100\,000$。本题不允许进行 Hack 操作。

我们称一个整数序列 $a_1, a_2, \ldots, a_n$ 为“距离凸”序列，如果对每个 $1 < i < n$ 都有 $|a_{i} - a_{i-1}| < |a_{i+1} - a_{i}|$。换句话说，如果你依次按顺序跳跃到 $a_1, a_2, \ldots, a_n$ 这些数轴上的点，每一次跳跃都比上一次要严格更远。

给定两个整数 $n$ 和 $m$。请你构造一个长度为 $n$ 的距离凸序列 $a$，其中最多包含 $m$ 个不同的数值。对于跳跃来说，这意味着你需要进行 $n-1$ 次跳跃，每次的距离严格递增，同时访问的不同点数不超过 $m$。保证所有 $1\leq i\leq n$ 都满足 $-10^{18} \leq a_i \leq 10^{18}$。

输入包含两个整数 $n$ 和 $m$，在一行中给出。

本题仅有两组测试数据。

• $n = 8$，$m = 6$；
• $n = 100\,000$，$m = 15\,000$。

保证这两组数据均存在解。本题不允许 Hack 操作。

输出一个长度为 $n$ 的距离凸序列 $a_1, a_2, \ldots, a_n$，该序列最多包含 $m$ 个不同的数，且对所有 $1\leq i\leq n$，$-10^{18} \leq a_i \leq 10^{18}$ 成立。

如果有多组满足条件的解，输出任意一组即可。

序列 $[1, 1, 3, 6, 10, 3, 11, 1]$ 的长度为 $n=8$，包含 $5$ 个不同的数，不超过 $m=6$。相邻元素之间的差值为 $0,2,3,4,7,8,10$，构成一个严格递增的数列。

$[1, 1, 2, 4, 8, 16, 32, 1]$ 也是一种合法解答。

由 ChatGPT 5 翻译