Palindromic Paths
Contest: Codeforces Round 580 (Div. 1)
Difficulty rating: 2400
Tags: implementation, interactive

This is an interactive problem

You are given a grid $$$n\times n$$$, where $$$n$$$ is odd. Rows are enumerated from $$$1$$$ to $$$n$$$ from up to down, columns are enumerated from $$$1$$$ to $$$n$$$ from left to right. Cell, standing on the intersection of row $$$x$$$ and column $$$y$$$, is denoted by $$$(x, y)$$$.

Every cell contains $$$0$$$ or $$$1$$$. It is known that the top-left cell contains $$$1$$$, and the bottom-right cell contains $$$0$$$.

We want to know numbers in all cells of the grid. To do so we can ask the following questions:

"$$$?$$$ $$$x_1$$$ $$$y_1$$$ $$$x_2$$$ $$$y_2$$$", where $$$1 \le x_1 \le x_2 \le n$$$, $$$1 \le y_1 \le y_2 \le n$$$, and $$$x_1 + y_1 + 2 \le x_2 + y_2$$$. In other words, we output two different cells $$$(x_1, y_1)$$$, $$$(x_2, y_2)$$$ of the grid such that we can get from the first to the second by moving only to the right and down, and they aren't adjacent.

As a response to such question you will be told if there exists a path between $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$, going only to the right or down, numbers in cells of which form a palindrome.

For example, paths, shown in green, are palindromic, so answer for "$$$?$$$ $$$1$$$ $$$1$$$ $$$2$$$ $$$3$$$" and "$$$?$$$ $$$1$$$ $$$2$$$ $$$3$$$ $$$3$$$" would be that there exists such path. However, there is no palindromic path between $$$(1, 1)$$$ and $$$(3, 1)$$$.

Determine all cells of the grid by asking not more than $$$n^2$$$ questions. It can be shown that the answer always exists.

Input format:
The first line contains odd integer ($$$3 \le n < 50$$$) — the side of the grid.

Interaction format:
You begin the interaction by reading $$$n$$$.

To ask a question about cells $$$(x_1, y_1), (x_2, y_2)$$$, in a separate line output "$$$?$$$ $$$x_1$$$ $$$y_1$$$ $$$x_2$$$ $$$y_2$$$".

Numbers in the query have to satisfy $$$1 \le x_1 \le x_2 \le n$$$, $$$1 \le y_1 \le y_2 \le n$$$, and $$$x_1 + y_1 + 2 \le x_2 + y_2$$$. Don't forget to 'flush', to get the answer.

In response, you will receive $$$1$$$, if there exists a path going from $$$(x_1, y_1)$$$ to $$$(x_2, y_2)$$$ only to the right or down, numbers in cells of which form a palindrome, and $$$0$$$ otherwise.

In case your query is invalid or you asked more than $$$n^2$$$ queries, program will print $$$-1$$$ and will finish interaction. You will receive Wrong answer verdict. Make sure to exit immediately to avoid getting other verdicts.

When you determine numbers in all cells, output "!".

Then output $$$n$$$ lines, the $$$i$$$-th of which is a string of length $$$n$$$, corresponding to numbers in the $$$i$$$-th row of the grid.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see documentation for other languages.

Hack Format

To hack, use the following format.

The first line should contain a single odd integer $$$n$$$ (side of your grid).

The $$$i$$$-th of $$$n$$$ following lines should contain a string of length $$$n$$$ corresponding to the $$$i$$$-th row of the grid. Top left element of the grid has to be equal to $$$1$$$, bottom right has to be equal to $$$0$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
3
0
1
0
1
1
1
1

Example output:
? 1 1 1 3
? 1 1 2 3
? 2 1 2 3
? 3 1 3 3
? 2 2 3 3
? 1 2 3 2
? 1 2 3 3
!
100
001
000

Editorial:
Denote $$$ ask ((x_1, y_1), (x_2, y_2)) = 1 $$$ if there is a palindromic path between them, and $$$ 0 $$$ otherwise. We also denote by $$$ grid [i] [j] $$$ the number written in the cell $$$ (i, j) $$$.
Firstly, make an observation: if the Manhattan distance is $$$ | x_2-x_1 | + | y_2-y_1 | = $$$ 2, then $$$ ask ((x_1, y_1), (x_2, y_2)) = 1 \iff board [x1] [y1] = board [x2] [y2] $$$. In fact, the path between the cells $$$ (x_1, y_1) $$$ and $$$ (x_2, y_2) $$$ has a length of $$$ 3 $$$, and therefore it is palindromic if and only if $$$ board [x1] [y1] = board [x2 ] [y2] $$$.
Consider a chessboard coloring such that the upper left unit is painted white. Then, using the observation described above, we can restore the numbers in all white cells. In a similar way, if we fix a certain number in a black cell, then all other numbers in black cells will be restored uniquely. Thus, we only have two options for arranging numbers on the board, which differ in the fact that in the second option, the numbers in the black cells are opposite to those in the first option. In the figure below, green pairs of white cells are connected, about which we can ask questions to find out all the values in them, and red - pairs of black cells.
Now there are two approaches. First: for each option, calculate $$$ ask ((x_1, y_1), (x_2, y_2)) $$$ for each pair of suitable cells, find where they differ, and ask a question about these two cells. This way we can uniquely identify the board option. It is possible to determine $$$ ask ((x_1, y_1), (x_2, y_2) $$$ using dynamic programming: the answer is $$$ 1 $$$ only when $$$ grid [x_1] [y_1] = grid [x_2] [y_2] $$$ and there is a path -palindrome between a pair of $$$ (x_1 + 1, y_1), (x_1, y_1 + 1) $$$ and $$$ (x_2-1, y_2), (x_2, y_2-1) $$$.
The second approach is a little more interesting, and it also shows why there is such a pair of cells for which the two options give different answers. Consider any path with a length of $$$ 4 $$$ cells, denote the numbers in its cells as $$$ c_1, c_2, c_3, c_4 $$$. Then two of the cells of the path are black, and two are white. We know the relation between $$$ c_1, c_3 $$$, as well as between $$$ c_2, c_4 $$$ (by the relation we mean that we know are numbers in them same, or different). Suppose that the relation between $$$ c_1, c_3 $$$ is the same as between $$$ c_2, c_4 $$$. Then $$$ ask (c_1, c_4) $$$ will make it possible to uniquely determine all the numbers! Indeed, if $$$ c_1 = c_4 $$$, then $$$ c_2 = c_3 $$$, and therefore the path will be palindromic. Otherwise, no path between $$$ c_1 $$$ and $$$ c_4 $$$ will be palindromic. Thus, we will be able to establish a relation between some white and some black cell, which will be enough to solve the problem.
Suppose that for any path of four cells $$$ c_1, c_2, c_3, c_4 $$$, the relation between $$$ c_1, c_3 $$$ is different from the relation between $$$ c_2, c_4 $$$. This is equivalent to $$$ c_1 \oplus c_2 \oplus c_3 \oplus c_4 = 1 $$$. Suppose that for any path of four cells $$$ \oplus $$$ of numbers in them is equal to $$$ 1 $$$. Then we consider any path from the cell $$$ (1, 1) $$$ to the cell $$$ (n, n) $$$ of length $$$ 2n-1 $$$. If the xor of each $$$ 4 $$$ of neighboring cells in it is $$$ 1 $$$, then the line is periodic with a period of $$$ 4 $$$, but the numbers in the first and last cell in it are different from the condition! Thus, the algorithm is as follows: choose any path between $$$ (1, 1) $$$ and $$$ (4, 4) $$$, find on it four cells with a xor of numbers equal to $$$ 0 $$$, and ask a question about it.
Asymptotics $$$O (n ^ 2) $$$.