Public Judge

pjudge

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 21776. 【PR #10】打摆

统计

本题是交互题。

有个 $100$ 个点的无向简单图。

你每次可以向交互库询问 $a, b, c$,交互库会告诉你 $a, b, c$ 三个点之间连了多少条边,并返回你一个 $\{0, 1, 2, 3\}$ 内的整数。你需要保证 $a,b,c$ 两两不同。

你需要复原出这张图。

实现细节

本题使用 IO 交互,你需要像传统题目一样提交一个可以编译的代码文件。

你初始不需要读入任何内容。你可以通过向标准输出中写入 ? a b c 来发起一次询问,随后从标准输入中读入一个 $0$ 到 $3$ 内的整数,表示交互库的回答。

当你能够复原这张图时,请输出一行 ! ,随后输出 $100$ 行,每行一个长度为 $100$ 的 $0/1$ 串 $s_i$ ,描述这张图。其中 $s_{i,j}$ 为 $1$ 当且仅当图中存在 $(i, j)$ 这条边。

记得在每次输出后 flush。

样例

为了方便,在样例里我们假设图中只有 $4$ 个点。注意在实际测试时图中会有 $100$ 个点。

选手输出 交互库输出
? 1 2 3 $ $
$ $ 0
? 1 2 4 $ $
$ $ 2
? 1 3 4 $ $
$ $ 2
! $ $
0001 $ $
0001 $ $
0001 $ $
1110 $ $

数据范围

所有测试点的图均有恰好 $100$ 个点。

设 $Q$ 表示你的询问次数。如果 $Q > 161 700$,或你返回的答案不正确,或你进行了不合法的交互过程,你获得 $0$ 分。

否则,你的得分将通过下表给出。

限制 得分
$9900 ≤ Q ≤ 161 700$ $10+10\cdot \frac{161700-Q}{161700-9900}$
$4950 ≤ Q ≤ 9900$ $20+10\cdot \frac{9900-Q}{9900-4950}$
$3400 ≤ Q ≤ 4950$ $30+10\cdot \frac{4950-Q}{4950-3400}$
$Q < 3400$ $100$

时间限制:$\texttt{1s}$

空间限制:$\texttt{512MB}$