题目背景

译自 ROI 2016 Day2 T2. Расшифровка ДНК

题目描述

这是一个交互式题目。

在鞑靼斯坦共和国境内进行考古发掘时，科学家们发现了一种未知古生物的遗骸，这种动物生活在数百万年前的喀山附近。与所有生物一样，这种生物的 DNA 分子由核苷酸序列组成，但其中不同种类核苷酸的数量可能与现代生物不同。

为了研究这一发现，科学家们制造了一种特殊的仪器，该仪器可以扫描 DNA 分子的核苷酸序列，并计算其中包含的不同种类核苷酸的数量。不幸的是，DNA 分子无法承受超过 $q$ 次扫描操作，之后就会被破坏。

研究人员希望借助该仪器来确定 DNA 中存在的不同核苷酸的数量 $k$，并找出 DNA 中哪些位置含有相同的核苷酸。科学家们想把核苷酸序列用正整数序列表示为 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le k$)，其中相同的数字表示相同的核苷酸，不同的数字表示不同的核苷酸。

你需要编写一个程序，与测试系统（评测程序）交互，以确定核苷酸的不同种类数量 $k$，以及表示 DNA 核苷酸序列的数列。

交互格式

在程序开始时，系统会提供一个整数 $n$——DNA 分子的长度（$1 \le n \le 3000$）。对于每个测试，参数 $k$（不同核苷酸的数量，$1 < k \le n$）和 $q$（最大允许的查询次数）都是固定的。保证给定的 $q$ 足以解决问题。

这些参数不会直接告知你的程序；评测系统在生成数据时会确保 DNA 序列中存在 $k$ 种不同的核苷酸。

如果你的程序进行了超过 $q$ 次查询，则会立即收到测试结果“Wrong Answer”（答案错误）。

为了进行一次查询，你的程序应输出一行形如：

? $i$ $j$

其中 $i$ 与 $j$ 为两个正整数，表示要对 DNA 中第 $i$ 个到第 $j$ 个位置（包含两端）的片段进行扫描，系统将返回一个整数 $p$——该片段中不同核苷酸的种类数（$1 \le i < j \le n$）。

评测系统会在查询结果所在的一行中输出该整数 $p$ 作为响应。

当程序已经获得足够的信息来恢复整个 DNA 序列时，应输出三行内容：

第一行输出：

Ready!

第二行包含 $k$，第三行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le k$），表示推断出的核苷酸序列。相同的数字应代表相同的核苷酸，不同的数字代表不同的核苷酸。如果存在多个可能的正确序列，则可以输出任意一个。

之后程序必须正常结束。

2
2

? 1 2
Ready!
2
1 2

3
1
2

? 1 2
? 1 3
Ready!
2
1 1 2

提示

样例解释

在第一个样例中，$n = 2$。只需一次查询就能判断第一个核苷酸和第二个核苷酸是否相同。

在第二个样例中，$n = 3$。第一次查询的结果表明前两个核苷酸相同；第二次查询的结果表明第三个核苷酸与前两个不同。因此有两种可能的正确答案：$1\ 1\ 2$ 或 $2\ 2\ 1$。

请严格遵守输出格式。每次输出后必须打印一个换行符，并刷新输出缓冲区。为此，在不同编程语言中应使用以下方法：

• 在 Pascal 或 Delphi 中使用 flush(output)；
• 在 C/C++ 中使用 fflush(stdout) 或 cout.flush()；
• 在 Python 中使用 sys.stdout.flush()；
• 在 Java 中使用 System.out.flush()。

数据范围

子任务编号	分值	限制条件	<		必须通过的子任务
		$n$	$k$	$q$
1	20	$1 \le n \le 300$	$1 \le k \le 2$	$q = 72000$
2	25		$1 \le k \le n$		1
3		$1 \le n \le 3000$
4	15				1–3
5				$q = 36000$	1–4

翻译由 ChatGPT-5 完成