cantor_ex

Description

There is a $N \times N$ lattice grid made up of integer points $(x,y)$ where $1 \leq x,y \leq N$. There is a hidden loop on the grid that passes through all $N^2$ points except for a single point.

More formally, the loop can be described by a sequence of points $p_1,p_2,\ldots,p_{N^2}$ where:

• $p_i=(x_i,y_i)$
• $1 \le x_i,y_i \le N$
• $p_1 = p_{N^2}$
• $p_i \neq p_j$ ($1 \leq i < j \leq N^2-1$)
• $|x_{i+1}-x_i|+|y_{i+1}-y_i|=1$ ($1 \leq i \leq N^2-1$)

Given the value of $N$, you will have to find the coordinates of the missing point using at most $37$ queries.

In one query you will give four integers $l,r,d,u$, where $l \le r$ and $d \le u$ and draw a rectangle with bottom-left corner $(l - 0.5, d - 0.5)$ and top-right corner $(r+0.5, u+0.5)$. You will be told the number of line segments that are contained inside the rectangle. A line segment $(p_i,p_{i+1})$ is contained inside the rectangle if at least one of $p_i$ or $p_{i+1}$ is contained inside the rectangle.

In the example below, the query gives four integers $2$, $3$, $3$, $5$ and the grader will return $6$.

The solid red line represents the loop, and the blue dashed line represents a rectangle from a query.

It can be shown that such a loop exists only if $N$ is odd.

Note that the grader is not adaptive: the loop is fixed before any queries are made.

Interaction

Your code should contain #include "cantor.h". It should not read from standard input or write to standard output as doing so would give Checker error verdict.

You should implement the following procedure:

pair<int,int> solve(int N)

• $3 \le N \le 999$
• $N$ is odd
• This function returns the coordinate of the point not in the loop.

You may make calls to the following procedure:

int count(int l,int r,int d,int u)

• This function will return the number of line segments that are contained inside the rectangle with bottom-left corner $(l - 0.5, d - 0.5)$ and top-right corner $(r+0.5, u+0.5)$.
• $l \leq r$ and $u \leq d$ must all be satisfied.
• This procedure should not be called more than $37$ times.

Sample Interaction

Suppose $N=5$ and the loop given is the same as the one shown in the example above.

The procedure solve is called below:

solve(5)

This procedure may call the procedure count some times.

The first call to count is called:

count(2,3,3,5)

The grader returns $6$.

The second call to count is called:

count(1,1,1,1)

The grader returns $2$.

The third call to count is called:

count(3,3,5,5)

The grader returns $0$.

Finally, the procedure determines that the point $(3,5)$ is not in the loop and returns solve returns $(3,5)$.

Sample Grader

A sample grader is provided in the attachments. The sample grader reads input in the following format:

• line $1$: $N$
• line $2$ to $N^2$: $x_i$ $y_i$

If your program is judged as accepted, the sample grader prints Accepted (X Queries Used) where $X$ is the number of queries used.

Otherwise, the grader prints Wrong Answer.