← 返回题目列表

Codeforces · 1254/C

C. 点订购

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

这是一个交互问题。

Khanh 在笛卡尔平面上有 $$$n$$$ 个点,用 $$$a_1, a_2, \ldots, a_n$$$ 表示。所有点的坐标均为 $$$-10^9$$$ 和 $$$10^9$$$(含)之间的整数。没有三点共线。他说这些点是凸多边形的顶点;换句话说,存在从 $$$1$$$ 到 $$$n$$$ 的整数排列 $$$p_1, p_2, \ldots, p_n$$$,使得多边形 $$$a_{p_1} a_{p_2} \ldots a_{p_n}$$$ 是凸的,并且顶点按逆时针顺序列出。

Khanh 为您提供数字 $$$n$$$,但隐藏了他的点的坐标。您的任务是通过询问多个查询来猜测上述排列。在每个查询中,您给出 Khanh $$$4$$$ 整数 $$$t$$$、$$$i$$$、$$$j$$$、$$$k$$$;其中 $$$t = 1$$$ 或 $$$t = 2$$$; $$$i$$$、$$$j$$$、$$$k$$$ 是从 $$$1$$$ 到 $$$n$$$(含)的三个不同索引。作为回应,Khanh 告诉你:

- 如果 $$$t = 1$$$,则三角形面积 $$$a_ia_ja_k$$$ 乘以 $$$2$$$。
- 如果 $$$t = 2$$$,则两个向量 $$$\overrightarrow{a_ia_j}$$$ 和 $$$\overrightarrow{a_ia_k}$$$ 的叉积的符号。

回想一下,向量 $$$\overrightarrow{a} = (x_a, y_a)$$$ 和向量 $$$\overrightarrow{b} = (x_b, y_b)$$$ 的叉积是整数 $$$x_a \cdot y_b - x_b \cdot y_a$$$。如果数字的符号是正数,则为 $$$1$$$,否则为 $$$-1$$$。可以证明,上述查询得到的叉积不可能是$$$0$$$。

您最多可以提出 $$$3 \cdot n$$$ 查询。

请注意,Khanh 固定了他的点的坐标,并且在回答您的问题时不会更改它。您不需要猜测坐标。在您的排列 $$$a_{p_1}a_{p_2}\ldots a_{p_n}$$$ 中,$$$p_1$$$ 应等于 $$$1$$$,并且顶点索引应按逆时针顺序列出。

互动

您可以通过读取 $$$n$$$ ($$$3 \leq n \leq 1\,000$$$) — 顶点数来开始交互。

要提出查询,请在单独的行中写入 $$$4$$$ 整数 $$$t$$$、$$$i$$$、$$$j$$$、$$$k$$$ ($$$1 \leq t \leq 2$$$、$$$1 \leq i, j, k \leq n$$$)。 $$$i$$$、$$$j$$$ 和 $$$k$$$ 应该不同。

然后读取单个整数以获得此查询的答案,如上所述。可以证明查询的答案始终是整数。

当你找到排列时,写一个数字$$$0$$$。然后在同一行写入 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ 。

打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

黑客格式

要破解,请使用以下格式:

第一行包含一个整数 $$$n$$$ ($$$3 \leq n \leq 1\,000$$$) — 顶点数。

接下来的 $$$n$$$ 行的第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$) — 点 $$$a_i$$$ 的坐标。

示例

输入 #1

6

15

-1

1

输出 #1

1 1 4 6

2 1 5 6

2 2 1 4

0 1 3 4 2 6 5

注意

下图显示了示例中的隐藏多边形:

示例中的交互如下:

- 参赛者读出$$$n = 6$$$。
- 参赛者提出一个查询,其中 $$$t = 1$$$、$$$i = 1$$$、$$$j = 4$$$、$$$k = 6$$$。
- 陪审团回答 $$$15$$$。三角形$$$A_1A_4A_6$$$的面积是$$$7.5$$$。请注意,答案是三角形面积的两倍。
- 参赛者提出以下查询:$$$t = 2$$$、$$$i = 1$$$、$$$j = 5$$$、$$$k = 6$$$。
- 陪审团回答 $$$-1$$$。 $$$\overrightarrow{A_1A_5} = (2, 2)$$$ 和 $$$\overrightarrow{A_1A_6} = (4, 1)$$$ 的叉积为 $$$-2$$$。 $$$-2$$$ 的符号是$$$-1$$$。
- 参赛者提出以下查询:$$$t = 2$$$、$$$i = 2$$$、$$$j = 1$$$、$$$k = 4$$$。
- 陪审团回答 $$$1$$$。 $$$\overrightarrow{A_2A_1} = (-5, 2)$$$ 和 $$$\overrightarrow{A_2A_4} = (-2, -1)$$$ 的叉积为 $$$1$$$。 $$$1$$$ 的符号是$$$1$$$。
- 参赛者说排列是 $$$(1, 3, 4, 2, 6, 5)$$$。