Paint
레이팅 미적용의견: 0
Croatian Olympiad in Informatics
October \(3^{rd}\) 2020
We will represent the drawing area of \(MS\) Paint as a rectangular grid of unit squares divided into \(R\) rows
and \(S\) columns. Each square of the grid represents a single pixel that can be colored in one of the \(10^{5}\)
different colors. When the user applies the so called bucket tool with color \(A\) on a pixel (r, s) which is
colored in the color \(B\), then all pixels in the monochrome neighborhood of pixel (r, s) change their color to
\(A\). Monochrome neighborhood of a pixel (r, s) is a set of pixels that are reachable by walking from (r, s)
in the four general directions (up, down, left and right) without changing the color of the pixel along the
way. Note that the pixel (r, s) is itself a part of its monochrome neighborhood.
You are given a starting image drawn in \(MS\) Paint along with \(Q\) instructions that should be executed
in the given order. Each instruction tells you on which pixel should you apply the bucket tool and with
what color. Your task is to how the image looks like after all instructions are executed.
Subtask
Score
Constraints
1
8
\(1 \le R \cdot S \le 10\,000\), \(1 \le Q \le 10\,000\)
2
9
\(R = 1\), \(1 \le S \le 200\,000\), \(1 \le Q \le 100\,000\)
3
31
\(1 \le R \cdot S \le 200\,000\), \(1 \le Q \le 100\,000\)
Each pixel will in every moment be colored either in color 0 or color 1.
4
52
\(1 \le R \cdot S \le 200\,000\), \(1 \le Q \le 100\,000\)
1 od 8
Croatian Olympiad in Informatics
October \(3^{rd}\) 2020
The first line contains integers \(R\) and \(S\) from the task description.
Each of the next \(R\) lines contains \(S\) n\(on-ne\)gative integers less than 100 000 that represent the starting
image drawn in \(MS\) Paint. More precisely, the \(j-th\) number in the \(i-th\) row of the image represents the
color of the pixel (i, j).
The next line contains an integer \(Q\) from the task description.
The \(i-th\) of the next \(Q\) lines contains integers \(r@@RISE_MATH_BLOCK_0@@i\) and \(c@@RISE_MATH_BLOCK_1@@i \le R\), \(1 \le s@@RISE_MATH_BLOCK_2@@i < 100\,000\)),
which represent the \(i-th\) instruction that tells you to use the bucket tool with color \(c@@RISE_MATH_BLOCK_3@@i\), s\(i\)).
You should output the final state of the image in the same format as it was given in the input.
12 11
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 0 0 1 1 1 1
1 1 1 0 0 0 0 0 1 1 1
1 1 0 0 0 0 0 0 0 1 1
1 0 0 0 2 2 2 0 0 0 1
1 0 0 0 2 2 2 0 0 0 1
1 0 0 0 2 2 2 0 0 0 1
1 0 0 0 0 0 0 0 0 0 1
1 1 0 0 0 2 0 0 0 1 1
0 1 1 0 0 2 0 0 1 1 0
0 0 1 1 0 0 0 1 1 0 0
0 0 0 1 1 1 1 1 0 0 0
2
5 5 3
6 2 41 1 1 1 1 1 1 1 1 1 1
1 1 1 1 4 4 4 1 1 1 1
1 1 1 4 4 4 4 4 1 1 1
1 1 4 4 4 4 4 4 4 1 1
1 4 4 4 3 3 3 4 4 4 1
1 4 4 4 3 3 3 4 4 4 1
1 4 4 4 3 3 3 4 4 4 1
1 4 4 4 4 4 4 4 4 4 1
1 1 4 4 4 2 4 4 4 1 1
0 1 1 4 4 2 4 4 1 1 0
0 0 1 1 4 4 4 1 1 0 0
0 0 0 1 1 1 1 1 0 0 04 4
1 0 1 3
1 3 2 2
3 3 1 2
2 2 1 3
3
1 2 3
3 2 1
4 2 31 1 1 3
1 1 2 2
1 1 1 2
3 3 1 36 6
1 2 1 2 2 2
3 1 2 1 3 1
3 3 2 3 2 2
2 3 1 3 3 2
3 3 3 3 3 3
2 3 2 2 2 1
4
6 2 2
3 5 2
3 2 3
1 2 31 3 1 2 2 2
3 1 3 1 3 1
3 3 3 3 3 3
3 3 1 3 3 3
3 3 3 3 3 3
3 3 3 3 3 1Clarification of the first example: The figure from the task description corresponds to the input of
the first example. White color corresponds to number 0, red color corresponds to number 1, blue color
corresponds to number 2, green color corresponds to number 3 and yellow color corresponds to number 4.
2 od 8
평가 및 의견
Paint
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Paint