C. Run, Fix, Repeat
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

This is an interactive problem with partial scoring.

You are only allowed to make one submission every 5 minutes, so you are encouraged to test your solution locally before submitting.

Cloudius is an extremely innovative company that builds super-innovative data centers. In fact, the level of innovation is so high that it can rebuild an entire data center in seconds. Every so often, a data center is spontaneously rebuilt to upgrade its architecture, enhance security, and keep the less innovative competition on its toes.

There's just one tiny issue: servers in a data center often break down, and fixer robots keep getting lost in the labyrinth of regenerated data centers. You are tasked with creating a new algorithm for these poor things.

In each test, a hidden data center layout is generated by the official generator (provided in "problem-c-generator.zip"). The layout is an $$$N \times N$$$ grid with $$$N = 125$$$ and contains a repair point that the fixer robot needs to find. Some cells contain server racks, and some are empty. The repair point can only be located in an empty cell.

You may make at most $$$T = 10000$$$ queries. Each query is represented by a pair of integers $$$(r, c)$$$. For a query $$$(r, c)$$$, the interactor responds with:

  • $$$-1$$$ if $$$(r, c)$$$ is a server rack.
  • $$$0$$$ if $$$(r, c)$$$ currently contains the repair point. Your score increases by $$$1$$$, and then the repair point moves to a uniformly random empty cell. Any empty cell, including the current one, may be chosen.
  • Otherwise, the length of the shortest path from $$$(r, c)$$$ to the repair point using only empty cells.

Your goal is to find the repair point as many times as possible in $$$T$$$ queries.

We have attached the generator in "problem-c-generator.zip" which uses a seed to produce the data center layout for a test. The official test set contains $$$50$$$ tests generated from random seeds fixed before the contest. Separately, we have attached "problem-c-example-tests.zip" with $$$10$$$ example tests generated as generator <seed> for seeds $$$1$$$ through $$$10$$$, so you can inspect them directly instead of generating them locally.

The repair point's positions are randomized independently for each run, so resubmitting the same solution may yield a different score.

Interaction

At the start, your program should read two integers:

  • $$$N$$$ — the size of the data center layout,
  • $$$T$$$ — the number of allowed queries.
In this problem, $$$N = 125$$$ and $$$T = 10000$$$ for all tests.

Then, repeat $$$T$$$ times:

  • print a query "r c" ($$$1 \le r, c \le N$$$),
  • flush the output,
  • read the interactor response.
Instead of a query, you may print "-1 -1" and stop the interaction early.

If the response is $$$0$$$, the repair point is found and immediately moves to a uniformly random empty cell.

Scoring

Your number of points for a test is calculated as follows:

  • If your program violates the interaction protocol or does not terminate correctly (e.g., exceeds the time or memory limit or produces a runtime error), your number of points for the test is $$$0$$$.
  • Otherwise, it is the number of times the repair point is found during the interaction process.

Your total number of points is the sum of your number of points across all $$$50$$$ tests.

Your final score is calculated as $$$800$$$ times the ratio of your total number of points to the highest total number of points among all participants: $$$800 \cdot \frac{\mathtt{your\_total\_points}}{\mathtt{best\_total\_points}}$$$.

Note that the scoreboard will consider your best score among all your submissions.

Problem by Nebius