Matrix Resurrection

Peregrine_Falcon National Girls' Programmi...

First, have a query for the upper left corner. Let the response be d1d1. Then query for the lower right corner of the grid. Let the response be d2d2. Draw a square from the upper left corner towards the lower right corner of size d1d1. Draw another square from the lower right corner towards the upper left corner of size d2d2. The squares maybe go outside of the actual grid. The two squares will always intersect each other. And the origin will be always within the intersected area.

There are a few cases we need to handle. If the squares intersect in a single cell, that is the origin cell. If the intersection points form a line horizontally or vertically, just query for any end of the line, you can easily find the origin cell by using the response.

What if the intersection points form neither a single point nor a line? If the intersected points form a rectangle, cause we are making the squares from the upper left and lower right corners of the grid, the origin will be either the upper right corner of the intersected rectangle or in the lower left corner of the intersected rectangle. We can check this with. only one query.

At most 3 queries in total.


50% Solution Ratio
IU_SpiralForgeEarliest, Nov '21
Azizul_cse27Fastest, 0.0s
Azizul_cse27Lightest, 5.5 kB
NOxBODYShortest, 663B
Toph uses cookies. By continuing you agree to our Cookie Policy.