← 返回题目列表

Codeforces · 2049/C

C. MEX 循环

中文机器翻译题面 查看原题

龙埃维里尔有很多朋友。他们有3个朋友!那比一般的龙还要多一头。

给定整数 $$$n$$$、$$$x$$$ 和 $$$y$$$。有 $$$n$$$ 龙围成一圈。龙的编号为 $$$1、2、\ldots、n$$$。对于每个 $$$i$$$ ($$$1 \le i \le n$$$),龙 $$$i$$$ 与龙 $$$i - 1$$$ 和 $$$i + 1$$$ 是朋友,其中龙 $$$0$$$ 被定义为龙 $$$n$$$,龙 $$$n + 1$$$ 被定义为龙 $$$1$$$。此外,龙 $$$x$$$ 和 $$$y$$$ 是彼此的朋友(如果它们已经是朋友,这不会改变任何事情)。请注意,所有友谊都是相互的。

输出 $$$n$$$ 非负整数 $$$a_1, a_2, \ldots, a_n$$$,这样对于每条龙 $$$i$$$ ($$$1 \le i \le n$$$),以下成立:

- 让$$$f_1、f_2、\ldots、f_k$$$成为龙$$$i$$$的朋友。然后 $$$a_i = \operatorname{mex}(a_{f_1}, a_{f_2}, \ldots, a_{f_k})$$$.$$$^{\text{*}}$$$

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行也是唯一一行包含三个整数 $$$n$$$、$$$x$$$、$$$y$$$ ($$$3 \le n \le 2 \cdot 10^5$$$、$$$1 \le x < y \le n$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,在满足语句中条件的行上输出 $$$n$$$ 空格分隔的非负整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$)。如果有多个解决方案,请打印其中任何一个。可以证明,在问题约束下,$$$0 \le a_i \le 10^9$$$ 的解总是存在。

示例

输入 #1

7
5 1 3
4 2 4
6 3 5
7 3 6
3 2 3
5 1 5
6 2 5

输出 #1

0 2 1 0 1
1 2 1 0
1 2 0 1 2 0
0 1 2 0 1 0 1
2 0 1
1 0 2 1 0
0 1 2 0 2 1

注意

对于第一个测试用例:

- $$$i = 1$$$:龙$$$1$$$的朋友是龙$$$2、3、5$$$。 $$$\operatorname{mex}(a_2, a_3, a_5) = \operatorname{mex}(2, 1, 1) = 0 = a_1$$$,因此满足龙$$$1$$$的条件。
- $$$i = 2$$$:龙$$$2$$$的朋友是龙$$$1、3$$$。 $$$\operatorname{mex}(a_1, a_3) = \operatorname{mex}(0, 1) = 2 = a_2$$$。
- $$$i = 3$$$:龙$$$3$$$的朋友是龙$$$1, 2, 4$$$。 $$$\operatorname{mex}(a_1, a_2, a_4) = \operatorname{mex}(0, 2, 0) = 1 = a_3$$$。
- $$$i = 4$$$:龙$$$4$$$的朋友是龙$$$3、5$$$。 $$$\operatorname{mex}(a_3, a_5) = \operatorname{mex}(1, 1) = 0 = a_4$$$。
- $$$i = 5$$$:龙$$$5$$$的朋友是龙$$$1、4$$$。 $$$\operatorname{mex}(a_1, a_4) = \operatorname{mex}(0, 0) = 1 = a_5$$$。