← 返回题目列表

AtCoder · arc154_d

D. A加B大于C吗?

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

分数: 700 点

问题陈述

PCT 有一个排列 (P_1,P_2,\dots,P_N) of (1,2,\dots,N)。您仅获悉 N.

你最多可以问他 25000 以下形式的问题。

  • 指定三个整数 (i,j,k) 这样 1 \le i,j,k \le N 并询问是否 P_i + P_j > P_k.

查找所有 P_1,P_2,\dots,P_N.

约束

  • 1 \le N \le 2000
  • P 是在程序和法官交互开始之前决定的。

输入和输出

这是一个交互式任务,您的程序和法官通过输入和输出进行交互。

首先,给出你的程序 N,排列的长度,来自标准输入:

N

然后,你可以提问。 按以下格式将您的问题打印到标准输出:(末尾应该有一个换行符。)

? i j k

如果问题有效,则答案 ans 将从标准输入给出:

ans

在这里, ans is Yes or No.

如果由于您提出的问题超出允许范围而导致问题格式错误或被判定为无效, -1 将从标准输入给出:

-1

这里,提交已经被判断为错误。此时法官将结束互动;最好,你的程序也应该退出。

一旦您确定了所有 P_1, P_2, \dots, P_N,按以下格式将它们打印到标准输出:(末尾应该有一个换行符。)

! P_1 P_2 \dots P_N

判断

  • 每次打印内容时,以换行符结束并刷新标准输出。否则,您可能会得到一个 TLE 判决。
  • 打印答案后(或收到 -1),立即正常终止程序。否则,判决将是不确定的。
  • 请注意,不必要的换行符将被视为格式错误的输出。

示例交互

以下是与 N = 4 和 P=(3,1,2,4).

输入 输出 说明
4 N 。
? 1 2 3 作为第一个问题,你问是否 P_1 + P_2 > P_3.
Yes 我们有 P_1 + P_2=4 和 P_3=2,所以答案是 Yes.
? 2 3 3 作为第二个问题,你问是否 P_2 + P_3 > P_3.
Yes 我们有 P_2 + P_3=3 和 P_3=2,所以答案是 Yes.
? 2 3 4 作为第三个问题,你问是否 P_2 + P_3 > P_4.
No 我们有 P_2 + P_3=3 和 P_4=4,所以答案是 No.
! 3 1 2 4 您打印 P_1,P_2,P_3,P_4。我们确实有 P=(3,1,2,4),所以你得到 AC.