cantor

cantor

Description

There is a lattice grid made up of integer points where . There is a hidden loop on the grid that passes through all points except for a single point.

More formally, the loop can be described by a sequence of points where:

  • ()
  • ()

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

In one query you will give four integers , where and and draw a rectangle with bottom-left corner and top-right corner . You will be told the number of line segments that are contained inside the rectangle. A line segment is contained inside the rectangle if at least one of or is contained inside the rectangle.

In the example below, the query gives four integers , , , and the grader will return .

img

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 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)

  • 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 and top-right corner .
  • and must all be satisfied.
  • This procedure should not be called more than times.

Sample Interaction

Suppose 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 .

The second call to count is called:

count(1,1,1,1)

The grader returns .

The third call to count is called:

count(3,3,5,5)

The grader returns .

Finally, the procedure determines that the point is not in the loop and returns solve returns .

Sample Grader

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

  • line :
  • line to :

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

Otherwise, the grader prints Wrong Answer.


Time Limit: 1 Seconds
Memory Limit: 1024MB
Your best score: 0
Source: TROC 24 (errorgorn)

Subtask Score
1 100