Background

Day 2 Problem C.

The statement is translated from EGOI2024 lightbulbs. The translation comes from ChatGPT and has been manually proofread. If there are any mistakes, please contact rui_er。

This problem is an interactive problem.

Problem Description

Soon after founding his light bulb company in Eindhoven in 1891, Frederik Philips made a great discovery: light bulbs that can light up infinite rays either horizontally or vertically. With this new discovery, he hopes to revolutionize modern home interior design.

He and his son Gerard are planning a complex installation. They installed $N^2$ light bulbs in an $N \times N$ grid in a room. They want to turn on as few bulbs as possible to light up the entire room, to save electricity. Each bulb is either vertical, meaning it lights up all cells in its column, or horizontal, meaning it lights up all cells in its row.

The figure below shows an example of a vertical bulb (left) and a horizontal bulb (right).

Unfortunately, while installing the bulbs, they did not pay attention and do not remember which bulbs are horizontal and which are vertical. Instead, they performed some experiments to figure out which bulbs to use to light up the entire room. Gerard stays in the room with the bulbs, while Frederik operates the switches from another room.

In each experiment, Frederik turns each bulb on or off, and Gerard reports how many cells are lit; cells lit by two or more different bulbs are counted only once. The number of bulbs turned on during an experiment does not matter, but they are short on time and ideally want to do as few experiments as possible.

Help them find a configuration that lights up the whole room using the minimum number of bulbs. They can perform at most $2000$ experiments. However, if you use fewer experiments, you will get a higher score.

---

Interaction

This is an interactive problem.

• Your program should first read an integer $N$, the height and width of the grid.
• Then, your program should interact with the judge. To perform an experiment, you should first print a line containing a question mark ?. In the next $N$ lines, output an $N \times N$ grid specifying which bulbs are turned on. Specifically, in each line, output a string of length $N$ consisting of 0 (off) and 1 (on). Then, your program should read an integer $l$ ($0 \le l \le N^2$), the number of cells lit by the specified bulbs.
• When you want to give your final answer, print a line containing an exclamation mark !, followed by $N$ lines in the same format as above. Before your answer is accepted, the bulbs must light up the entire grid, and the number of bulbs turned on must be minimal.

After that, your program should terminate.

The judge is non-adaptive, meaning the bulb grid is fixed before the interaction starts.

After each experiment, make sure to flush standard output; otherwise, your program may be judged as TLE. In Python, using input() to read a line will automatically flush. In C++, cout << endl; both prints a newline and flushes; if you use printf, use fflush(stdout)。

Input Format

See the “Interaction” section.

Output Format

See the “Interaction” section.

5






10






13

?
11000
00000
00000
00000
00000

?
01000
01000
01000
00100
00000

!
00100
00010
01000
00001
01000

Hint

Sample explanation

In the sample interaction, the program first reads the grid size $N = 5$. The figure below shows the hidden grid (unknown to the program) and one of many possible solutions that lights up the entire grid using five bulbs. The marked bulbs are turned on, and the darker squares are lit.

The program performs the two experiments shown below. In the first experiment, the two vertical bulbs in the top-left corner light a total of 10 cells. The second experiment lights a total of 13 cells. Finally, the program outputs its answer (as shown above) and terminates.

---

Constraints

For all testdata, $3\le N\le 100$. You may perform at most $2000$ experiments (outputting the final answer does not count as an experiment). If you exceed the limit, your program will be judged WA.

• Subtask 1 ($11$ points): $N=3$.
• Subtask 2 ($11$ points): $N\le 10$.
• Subtask 3 (up to $78$ points): no additional constraints.

Note: Some test points were placed in multiple subtasks in EGOI. To save judging resources and reduce the workload of organizing the data, these test points are included under the smallest-numbered subtask among all subtasks that contain them. This may cause a solution to get a higher score than expected, but it cannot pass the problem.

---

Scoring

In Subtask 3, you are scored based on the number of experiments according to the formula below:

$$\textrm{score}= \begin{cases} (2000-Q)\cdot 29/900&\text{if }200\le Q\le 2000\\ 58+(200-Q)\cdot 4/23&\text{if }85\le Q\le 200\\ 78&\text{if }Q\le 85\\ \end{cases}$$

Here $Q$ is the maximum number of experiments among all test points in this subtask. Your score will be rounded to the nearest integer.

Below is the graph of the total score as a function of $Q$ in Subtask 3. To get full points, you need to solve every test point in Subtask 3 using no more than $85$ experiments.

Translated by ChatGPT 5