← 返回题目列表

AtCoder · ttpc2024_1_i

I. 近对

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

分数: 100 点

问题陈述

这是一个 交互问题,你的程序通过标准输入和输出与裁判系统交互。

给你整数 N, K,和 Q.
裁判持有一个隐藏的排列。 (a_1, a_2, \dots, a_N) of (1, 2, \dots, N).
你最多可以向裁判提出 Q 次查询,每次查询如下:

  • 选择一个子集 S 来自 \lbrace 1, 2, \dots, N \rbrace。裁判将返回不同对的数量 (i, j) 这样 i < j 和 |a_i - a_j| \leq K 其中 i, j \in S.

让 x 是索引 t 其中 a_t = 1,和 y 是索引 t 其中 a_t = N。 你的任务是确定该集合 \lbrace x, y \rbrace。(你不需要区分哪一个是 x ,哪一个是 y.)

。法官是非自适应的,这意味着排列 (a_1, a_2, \dots, a_N) 在任何交互开始之前就已经固定。

约束

  • 所有输入值均为整数。
  • N = 20000
  • 1 \leq K \leq 10
  • Q = 30(K + 1)

部分分数

30 分将被授予给满足附加约束条件的测试集合的通过者 K = 10.


输入和输出

这是一个交互问题。

首先,读取整数 N, K,和 Q 从标准输入:

N K Q

然后,重复以下过程,直到你找到集合 \lbrace x, y \rbrace:

对于查询,将以下格式输出到标准输出:

? s_1s_2 \dots s_N

在这里, s_1 s_2 \dots s_N 是长度为的二进制字符串 N 表示子集 S,其中 s_i = {}1 if i \in S,和 s_i = {}0 否则。

对您的查询的响应将以以下格式提供在标准输入中:

T

在这里, T 是查询的答案,表示不同对的数量 (i, j) 这样 i < j 和 |a_i - a_j| \leq K 其中 i, j \in S.

一旦您确定集合 \lbrace x, y \rbrace,以以下格式输出两个元素(顺序无关),并立即终止您的程序:

! x y

注释

  • 在每条消息的末尾打印换行符并刷新标准输出。否则,您可能会得到一个 TLE 判决。
  • 如果您的查询格式无效或超出查询次数,评测程序将响应 T = -1。如果您收到此响应,您应该立即终止程序。否则,您可能会得到一个 TLE 判决。
  • 请注意,不必要的换行符被视为格式错误。

示例交互

以下是一个示例交互: N = 5, K = 2, Q = 90。请注意,这个例子不符合约束条件,因此不会出现在测试用例中。

输入 输出 说明
裁判持有该排列 (3, 5, 2, 1, 4).
5 2 90 首先,整数 N, K,和 Q 。
? 11000 你查询 S = \lbrace 1, 2 \rbrace.
1 只有这一对 (1, 2) 满足条件,因此裁判回应 1.
? 10011 你查询 S = \lbrace 1, 4, 5 \rbrace.
2 对 (1, 4) 和 (1, 5) 满足条件,因此裁判回应 2.
! 2 4 你输出 \lbrace 2, 4 \rbrace 作为答案。因为 a_4 = 1 和 a_2 = N,这个输出是正确的。