FloodFill
SRM 794 · 2020-11-24 · by misof
Problem Statement
There is an infinite square grid. Initially, the whole grid is dry, except for some cells that contain water sources. For each valid i, one of the water sources is the cell (X[i], Y[i]).
All water sources will start flooding the plane at the same time. The flood proceeds from each water source in all eight directions at a speed of one cell per second. (I.e., during each second all dry cells that share a side or a corner with a flooded cell will become flooded.)
Suppose we order all cells other than the water sources by the time when they were flooded, breaking ties lexicographically (smaller x, then smaller y). Return the coordinates of the A-th cell in this sequence (counting from 1).
Constraints
- X will contain between 1 and 30 elements, inclusive.
- Y will contain the same number of elements as X.
- Each element of X and Y will be between 0 and 10^8, inclusive.
- All cells described by X and Y will be distinct.
- A will be between 1 and 10^16, inclusive.
{4, 5}
{7, 2}
1
Returns: {3, 6 }
The water sources are in the cells (4, 7) and (5, 2). The lexicographically smallest cell flooded during the first second is the cell (3, 6)
{4, 5}
{7, 2}
8
Returns: {4, 8 }
After (3, 6) from the previous example, the following cells (all of them also flooded during the first second) are (3, 7), (3, 8), (4, 1), (4, 2), (4, 3), (4, 6) and (4, 8). Note that the initial cell (4, 7) does not get flooded again.
{4, 5}
{7, 2}
17
Returns: {2, 5 }
Still the same two water sources. Cell number 17 is the lexicographically smallest among cells that were flooded during the second second.
{4, 5}
{7, 2}
53
Returns: {1, 8 }
The fifth lexicographically smallest cell among those flooded during the third second.
{4, 5}
{7, 2}
84
Returns: {8, 5 }
The lexicographically last cell flooded during the third second.
{0}
{0}
123456789012
Returns: {64258, -175682 }
The cells flooded during second number 175682 form the boundary of a large square with cells (-175682,-175682) and (175682,175682) in opposite corners. The cell we seek is one of these cells.
{0, 0, 0, 1, 1, 2, 2, 2}
{0, 1, 2, 0, 2, 0, 1, 2}
17
Returns: {3, 3 }
Exactly 17 cells get flooded during the first second. Note that the cell (1, 1) only gets flooded once, even though it is adjacent to four water sources.
Submissions are judged against all 88 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FloodFill with a public method vector<int> getCell(vector<int> X, vector<int> Y, long long A) · 88 test cases · 2 s / 256 MB per case