链接: https://cses.fi/problemset/task/3228

板块: Interactive Problems

时限: 1.00 s ｜ 内存: 512 MB

题目描述

有一个隐藏的排列 $a_1, a_2,\dots, a_n$，由整数 $1, 2,\dots, n$ 组成。你的任务是求出这个排列。

为此，你可以进行提问：选择一个二进制串 $b_1b_2\dots b_n$，你将收到二进制串 $b_{a_1}b_{a_2}\dots b_{a_n}$。

输入

这是一个交互题。你的程序将通过标准输入和输出与评测机进行交互。你应当先读取一个整数 $n$：排列的长度。

在你的回合中，你可以输出以下内容之一：

• ? b_1b_2\dots b_n，其中 $b_i \in \{0, 1\}$：评测机将返回二进制串 $b_{a_1}b_{a_2}\dots b_{a_n}$。
• ! a_1 a_2 \dots a_n：报告隐藏的排列为 $a_1, a_2,\dots, a_n$。输出此行后你的程序必须终止。

每行输出后都应跟一个换行符。你必须确保每行输出后都刷新缓冲区。

输出

参见上述交互协议。

数据范围

$1 \le n \le 1000$ 你最多可以进行 $10$ 次类型为 ? 的提问

样例

3
? 100
100
? 010
001
? 001
010
! 1 3 2

说明：隐藏的排列为 $[1, 3, 2]$。在第一个问题中 $b_1b_2b_3 = 100$，评测机返回 $b_{a_1}b_{a_2}b_{a_3} = b_1b_3b_2 = 100$。在第二个问题中 $b_1b_2b_3 = 010$，评测机返回 $b_1b_3b_2 = 001$。