← 返回题目列表

AtCoder · joigsp2025_d

D. 太空窃贼

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

配点: 100 点

配布fiiru

注意

  • 300 进行回的查询时,将以评测方和输入输出的总和消耗最多 1200 毫秒。
  • 由于测试用例数量较多,对于无法得到正确答案的输入,建议提前终止。

你在 JOI 银河活跃,作为怪盗。

JOI 银河中有 0 到 N - 1 编号为的 N 颗星。还0 到 M - 1 编号为的 M 有一个跳跃装置。跳跃装置 i (0 \leqq i \leqq M - 1)在星 U_i 和星 V_i 之间双向连接。无论哪 2 个星星之间,都可以通过使用几个跳跃装置移动。

在打飞机银河的某颗星上隐藏着钥匙,在其他星星上隐藏着宝箱。你的任务是确定隐藏钥匙和宝箱的星号。为此,可以进行以下质询 300 可以进行回数。

  • 每个传送装置 i (0 \leqq i \leqq M - 1)关于,从星球 U_i 到星球 V_i 只连方向,或者选择只连向星球 V_i 到星球 U_i 方向。
  • 在此基础上,询问是否可以使用几个传送装置从有钥匙的星球移动到有宝箱的星球。

你希望通过质问来确定钥匙所隐藏的星星编号 A 和宝箱所隐藏的星星编号 B 。为了在任务中获得高评价,希望质问的次数尽可能少。

当银河的信息被提供时,通过质问可以得知钥匙所隐藏的星星编号 A 和宝箱所隐藏的星星编号 B 的策略。


入出力

这个问题是 互动问题(您创建的程序和判断程序通过标准输入和输出交互的问题)。

首先,星系信息以以下格式从标准输入给出。

N M
U_0 V_0
U_1 V_1
\vdots
U_{M-1} V_{M-1}

您的程序收到此消息后,必须与评分程序进行交互。

要提出问题,请按照以下格式与评分程序交互。

  • 首先,按以下格式输出到标准输出。 关于
    ? x_0 x_1 x_2 \cdots x_{M - 1}
    • 0 \leqq i \leqq M - 1 ,x_i 是一个字符 0 或 1 和这些之间没有空格的长度 输出为 M 字符串 (请仅在(? 之后插入一个空格)。 该字符串的长度是 如果不是 M ,不正解 [1] 已确定。
    • 0 \leqq i \leqq M - 1 ,x_i 是 0 但是 如果不是 1 , 当不正解 [2] 已确定。
    • 0 \leqq i \leqq M - 1 ,x_i 是 0 时扭曲装置 关于 i ,星 要单向连接到 U_i 到星球 V_i , 表示单向连接到1 时扭曲装置 关于 i ,星 要单向连接到 V_i 到星球 U_i 。
  • 然后是一个代表问题答案的整数。 r 由标准输入以以下格式给出。
    r

    在这里,r 是 0, 1, -1 ,分别代表以下内容。 当
    • r 是 0 时,星星 表示无法移动到 A 到星球 B 。 表示您可以移至
    • r 是 1 时,星星 表示无法移动到 A 到星球 B 。
    • r 是 -1 表示评分程序判定您的程序不正确。在这种情况下,请立即终止您的程序。

问一个问题 请勿超过 300 次。 如果执行次数超过300 次,不正解 [3] 已确定。

要回答隐藏钥匙的星星的编号和隐藏宝箱的星星的编号,请按以下格式将其输出到标准输出。

! A B
  • A 是 0 以上 N - 1 是下面的整数。带隐藏钥匙的星号 A 。
  • A 是0 以上 N - 1 。如果不满足这一点, 它是小于或等于不正解 [4] 已确定。
  • B 是 0 以上 N - 1 的整数。宝箱隐藏的星星编号 B 。
  • B 是0 以上 N - 1 。如果不满足这一点, 它是小于或等于不正解 [5] 已确定。
  • 如果您回答错误的星星号码,不正解 [6] 已确定。
  • 答案就是 必须执行 1 次。 如果您回答的次数超过2 次,不正解 [7] 被确定。在程序执行结束时答案是 如果尚未执行 1 次,不正解 [8] 已确定。

如果以上述任何格式以外的格式输出到标准输出,不正解 [9] 已确定。

重要说明

  • 确保在每个输出结束时刷新标准输出。如果不flush,可能会判定已经超出了执行时间限制。
  • 提交C++程序时,cout << endl; 会产生新行并自动刷新。如果 当使用 printf 时, 使用fflush(stdout) 。
  • 提交Python程序时,输入 只要你使用 input() ,就会自动刷新。
  • 提问时 如果您收到 -1 ,请立即退出程序。如果未完成,则执行结果不确定。

评分注意事项

对于某些测试用例,实际评分程序是自适应的。这意味着评分程序从一开始就没有固定的答案,而是根据之前的问题进行响应。但是,如果与所有响应一致的答案至少是 1 保证存在。


测试工具

用于测试创建的程序的测试工具 testing_tool.py 包含在可以从竞赛网站下载的存档中。并非必须使用该工具,并且允许对其进行修改。请注意,实际评分程序与测试工具不同。特别是,测试工具不具有适应性,从一开始就有固定的答案。

如果您的程序是用C++实现的,您可以按照以下步骤进行测试。

  • 编译程序并生成可执行文件。例如,如果您的程序 如果名称为 thief.cpp ,则可以运行以下命令。 将生成一个名为 thief 的可执行文件。

    g++ -std=gnu++20 -O2 -o thief thief.cpp

  • 接下来,执行以下命令。

    python3 testing_tool.py ./thief

如果你的程序是用Python实现的,例如 如果名称为 thief.py ,则运行以下命令。

python3 testing_tool.py pypy3 thief.py

测试工具输入

测试工具按以下格式从标准输入读取输入。

N M A B
U_0 V_0
U_1 V_1
\vdots
U_{M-1} V_{M-1}

测试工具输出

如果程序执行正常结束,则测试工具将以下信息输出到标准输出(引号实际上不输出)。

  • 如果答案正确,则提出的问题数为 Accepted: 25 。
  • 如果答案不正确,则错误答案的类型为 Wrong Answer [4] 。

如果要执行的程序满足多个错误答案条件,则显示的错误答案类型将是其中之一。 1 只有一个。


制約

所有输入数据满足以下条件。

  • 2 \leqq N \leqq 10\,000.
  • 1 \leqq M \leqq 15\,000.
  • 0 \leqq A \leqq N - 1.
  • 0 \leqq B \leqq N - 1.
  • A \neq B.
  • 0 \leqq U_i < V_i \leqq N - 1 (0 \leqq i \leqq M - 1).
  • (U_i, V_i) \neq (U_j, V_j) (0 \leqq i < j \leqq M - 1).
  • 哪个 2 个星星之间,都可以通过使用几个跳跃装置移动。
  • 所有输入值均为整数。

小課題

  1. (11 点) M = N - 1,U_i = i,V_i = i + 1 (0 \leqq i \leqq M - 1).
  2. (21 点) M = N - 1,U_i = 0,V_i = i + 1 (0 \leqq i \leqq M - 1).
  3. (4 点) M = N - 1,N \leqq 8.
  4. (12 点) M = N - 1,N \leqq 50.
  5. (8 点) M = N - 1,N \leqq 150.
  6. (8 点) M = N - 1,N \leqq 250.
  7. (32 点) M = N - 1.对于此子任务,将根据以下方式确定分数: 对于
    • 小課題 7 对应的测试用例,1 如果您得到任何错误答案,您在此子任务的得分将为 0 成为重点。
    • 否则,该函数 query 的最大调用次数为 T 。此时,子任务的分数确定如下。
      • 120 < T 时,16 点.
      • 70 < T \leqq 120 时,24 点.
      • T \leqq 70 时,32 点.
  8. (4 点)没有额外的限制。对于此子任务,将根据以下方式确定分数:
    • 小課題 8 对应的测试用例,1 如果您得到任何错误答案,您在此子任务的得分将为 0 成为重点。
    • 否则,该函数 query 的最大调用次数为 T 。此时,子任务的分数确定如下。
      • 120 < T 时,2 点.
      • 70 < T \leqq 120 时,3 点.
      • T \leqq 70 时,4 点.

小課題 1,2,3,4,5,6 的分数不取决于提出的问题数量 (300 次或更少),但是 如果超过70 次,竞赛网站可能会表明输出部分正确。


交互示例

测试工具读取的输入示例和相应的交互如下所示。

入力例 1

5 4 0 4
0 1
0 3
1 2
1 4
7be724b9ba153c7baf9de60727f76fc6.png

1 第二题对应的选择如下。

  • 扭曲装置 沿一个方向连接至 0 ,星 要单向连接到 0 到星球 1 。
  • 扭曲装置 沿一个方向连接至 1 ,星 要单向连接到 3 到星球 0 。
  • 扭曲装置 沿一个方向连接至 2 ,星 要单向连接到 1 到星球 2 。
  • 扭曲装置 沿一个方向连接至 3 ,星 要单向连接到 1 到星球 4 。

在此选择下,明星 0 到星球 4 扭曲装置 您可以按此顺序使用 0, 3 进行移动,因此返回值为 由于使用某些扭曲设备无法前往 1 变为。

2 第二题对应的选择如下。

  • 扭曲装置 沿一个方向连接至 0 ,星 要单向连接到 1 到星球 0 。
  • 扭曲装置 沿一个方向连接至 1 ,星 要单向连接到 3 到星球 0 。
  • 扭曲装置 沿一个方向连接至 2 ,星 要单向连接到 2 到星球 1 。
  • 扭曲装置 沿一个方向连接至 3 ,星 要单向连接到 1 到星球 4 。

在此选择下,明星 0 到星球 4 ,因此返回值为 由于可以使用多个扭曲设备前往 0 变为。

3 第二题对应的选择如下。

  • 扭曲装置 沿一个方向连接至 0 ,星 要单向连接到 0 到星球 1 。
  • 扭曲装置 沿一个方向连接至 1 ,星 要单向连接到 0 到星球 3 。
  • 扭曲装置 沿一个方向连接至 2 ,星 要单向连接到 2 到星球 1 。
  • 扭曲装置 沿一个方向连接至 3 ,星 要单向连接到 1 到星球 4 。

在此选择下,明星 0 到星球 4 ,因此返回值为 1 变为。

4 在第问题对应的选项下,星星 0 到星球 4 ,因此返回值为 由于可以使用多个扭曲设备前往 0 变为。

最后是星星 A 是一颗星星 0 和一颗星星 答案是 B 是一颗星星 4 。

此输入示例是一个小作业。 3,4,5,6,7,8 满足约束。在可以从竞赛网站下载的存档中包含的文件中,sample-01-in.txt 是一个输入示例 对应于 1 。