Background

Translated from CEOI 2013 Day 1.

This is an interactive IO task.

After an earthquake, a new island appeared in the Adriatic Sea. A special device was found on the island, called the “Oracle”. Although there was no manual, a team of archaeologists and computer experts managed to understand how it works.

The Oracle provides some information about the locations of treasures on the island. The island is divided into an $N$ by $N$ grid, with both rows and columns numbered from $1$ to $N$. Some cells in the grid contain treasures. The Oracle only answers questions of the following form: “Given a rectangle in the grid, how many cells in this rectangle contain treasures?”

Although the Oracle can answer rectangle queries of any size, it was discovered that the more specific the requested information is (the smaller the rectangle is), the more energy the Oracle consumes when answering. More precisely, if a rectangle contains $S$ cells, then the Oracle will use $1 + N \times N - S$ units of energy to answer.

Problem Description

Write a program that determines the positions of all cells on the island that contain treasures by interacting with the Oracle. We do not want to use too much energy during this process: the less energy used, the better. However, you are not required to minimize the energy usage; see “Hint” at the end for the scoring rules.

This is an interactive task. Your program asks the Oracle by writing to standard output, and obtains answers by reading from standard input.

• At the start of the program, it should read an integer $N$ ($2 \leq N \leq 100$), the size of the grid.
• To ask the Oracle, your program should output one line containing $4$ integers $R_1$, $C_1$, $R_2$, and $C_2$, separated by spaces, such that $1 \leq R_1 \leq R_2 \leq N$ and $1 \leq C_1 \leq C_2 \leq N$. If these conditions do not hold, or the line format is incorrect, your program will receive $0$ points on that test run.
• The Oracle will respond with a line containing a single integer: the number of cells containing treasures inside the given rectangle. More precisely, it is the number of cells $(R, C)$ such that $R_1 \leq R \leq R_2$ and $C_1 \leq C \leq C_2$, and the cell in row $R$ and column $C$ contains a treasure.
• When the program finishes asking questions (i.e., it has determined the positions of all treasures), it should output END on a new line. Then output $N$ lines, each a string of $N$ characters 0 or 1. The $C$-th character of line $R$ is 1 if the cell in row $R$ and column $C$ contains a treasure, and 0 otherwise. Rows are numbered from top to bottom as $1$ to $N$, and columns are numbered from left to right. Once your program outputs the solution, its execution will be terminated automatically.

To interact correctly with the judge, you must flush standard output after each query and after printing the final solution, as is customary for interactive tasks.

In each test run, you may assume the Oracle always answers correctly, and the treasure locations are fixed before interaction. In other words, the answers do not depend on the questions previously asked (the Oracle will not change the answer based on your queries); the correct grid is fixed for each test case.

Input Format

This task is an interactive task. To complete it successfully, you need to write a program to minimize the number of queries to the Oracle and the energy used as much as possible. At the start of the program, the input provides the island size $N$.

Output Format

Query the Oracle for the number of treasure cells by outputting row and column indices. After your program has obtained enough information, output END, then output the final grid of treasure positions. The final score is determined by the total energy used by the Oracle. The exact scoring rules are given at the end of the statement, and the detailed format can be seen in the sample input/output.

2
0
1
2

1 1 1 1
1 2 1 2
2 1 2 2
END
01
11

Hint

Sample explanation

Each test case is worth $10$ points. If your program’s output is incorrect, it gets $0$ points for that test case. Otherwise, the score is determined by the total number of energy units used by the Oracle, denoted by $K$.

Specifically:

• If $K \leq \frac{7}{16} N^4 + N^2$, you get $10$ points.
• Otherwise, if $K \leq \frac{7}{16} N^4 + 2N^3$, you get $8$ points.
• Otherwise, if $K \leq \frac{3}{4} N^4$, you get $4$ points.
• Otherwise, if $K \leq N^4$, you get $1$ point.
• Otherwise, you get $0$ points.

Also, in testdata that accounts for at least $40\%$ of the total score, $N$ will be at most $20$.

In summary, the less energy you spend, the higher your score will be.

Interactive library / SPJ provider:

Translated by ChatGPT 5