P10831 [COTS 2023] Triangle Trokuti

Translated from [Izborne Pripreme 2023 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2023/) D1T3. $\texttt{1s,0.5G}$. Happy birthday to NaCly_Fish! (2024.7.28).

**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++.

See [Implementation Details].

See [Implementation Details].

#### 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: | $Q$ | Score | |:-----:|:------:| | $9\, 900\le Q\le 161\, 700$ | $\displaystyle 10+10\cdot \frac{161\, 700-Q}{161\, 700-9\, 900}$ | | $4\, 950 \le Q\le 9\, 900$ | $\displaystyle 20+10\cdot \frac{9\, 900-Q}{9\,900-4\,500}$ | | $3\, 400\le Q\le 4\, 950$ | $\displaystyle 30+70\cdot \frac{4\,950-Q}{4\,950-3\,400}$ | | $Q\le 3\, 400$ | $100$ | Translated by ChatGPT 5