Background

Translated from Izborne Pripreme 2023 (Croatian IOI/CEOI Team Selection) D1T3. $\texttt{1s,0.5G}$.

Happy birthday to NaCly_Fish! (2024.7.28).

Problem Description

This is an interactive problem. The interactive library is non-adaptive.

There is a hidden simple undirected graph $G$ with exactly $N=100$ nodes. Your task is to reconstruct $G$ using the following type of query:

Query Given three pairwise distinct nodes $u,v,w$, the judge returns the number of edges in the induced subgraph on these three nodes. Note that the answer can only be $0,1,2,3$.

[Implementation Details]

Your program interacts with the judge through standard input and output.

• $\texttt{? u v w}$: Make one query. The judge replies (read from standard input) with the number of edges in the induced subgraph on $u,v,w$. Note that the answer can only be $0,1,2,3$.

  You must ensure $1\le u,v,w\le 100$, and $u,v,w$ are pairwise distinct. You may ask at most $161\, 700$ queries.

• $\texttt{!}$: Output your final answer. After outputting $\texttt{!}$ and a newline, output $N$ lines, each being a $\texttt{01}$ string of length $N$.

  The $j$-th character in the $i$-th line is $\texttt{1}$ if there is an edge between $(i,j)$; otherwise it is $\texttt{0}$.

After each output, you must flush the buffer, e.g. cout.flush() in C++.

Input Format

See [Implementation Details].

Output Format

See [Implementation Details].

0

2

2

? 1 2 3

? 1 2 4

? 1 3 4

!
0001
0001
0001
1110

Hint

Scoring

Let $Q$ be the maximum number of queries your program makes.

If $Q\gt 161\, 700$, you get $0$ points.

Otherwise, your score is determined by the following table:

Translated by ChatGPT 5