QOJ.ac

QOJ

时间限制: 3 s 内存限制: 256 MB 总分: 100 交互

#8469. 喜剧并非万能

统计

这是一个交互式问题。

Vim、Emacs 和 Nano 正在玩一个猜谜游戏。Vim 秘密地告诉了 Nano 一个长度为 $n$ 的随机二进制序列 $\{a_i\}$。Emacs 可以向 Nano 查询一个下标集合 $I \subseteq \{1, 2, \dots, n\}$。Nano 将会回复 $\sum_{i \in I} a_i$ 的值。请你帮助 Emacs 在少于 $n/2$ 次查询内找出 $\{a_i\}$。此外,所有查询中集合大小的总和不得超过 $3n$。

交互格式

输入的第一行包含一个整数 $n$。

你可以使用以下任一操作并将其写入标准输出:

  1. “? $k \ i_1 \ i_2 \ \dots \ i_k$”:发送一个查询,其中 $I = \{i_1, i_2, \dots, i_k\}$。这些元素必须互不相同。Nano 将会把结果写回标准输入。查询次数必须少于 $n/2$,且所有查询中 $k$ 的总和不得超过 $3n$。
  2. “= $a_1a_2 \dots a_n$”:提交你找到的二进制序列 $\{a_i\}$。注意 $a_i$ 之间没有空格。你的程序在执行此操作后必须正常退出。

请记住在每次操作后换行并刷新标准输出。例如,在 C 或 C++ 中可以使用 fflush(stdout),在 Java 中可以使用 System.out.flush(),在 Pascal 中可以使用 flush(output),或者在 Python 中使用 sys.stdout.flush()

样例

输入格式 1

4
2
1
2

输出格式 1

? 4 1 2 3 4
? 2 1 2
? 2 2 3
= 0110

说明

在所有测试中,$n = 10^5$。$n = 4$ 的样例仅用于展示格式,不会被测试。

本题最多有 50 组测试数据。测试数据是随机生成的,但已预先固定。在每组测试中,每个长度为 $n$ 的二进制序列被生成的概率均为 $1/2^n$。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.