AT_masters2026_final_a Copy-Paste Painting (A)

Master painter Takahashi is working on a new piece of art using image editing software. While creating the work, he can use multiple layers, gradually add to the image, rotate and overlay the contents of another layer, or clear a layer that is no longer needed. Your task is to find a procedure that completes the target image in as few operations as possible.

There are $ K $ layers, each consisting of $ N\times N $ pixels. The layers are numbered $ 0,\cdots,K-1 $ . Let the coordinates of the top-left pixel be $ (0,0) $ , and define the coordinates of the pixel reached by moving $ i $ pixels downward and $ j $ pixels to the right from there as $ (i,j) $ . There are $ C $ available colors, numbered $ 1,\cdots,C $ . Let $ c(k,i,j) $ denote the color of pixel $ (i,j) $ on layer $ k $ . If $ c(k,i,j)=0 $ , that pixel is transparent. The target image is given by the color $ g_{i,j} $ of each pixel. The target image is considered complete when $ c(0,i,j)=g_{i,j} $ holds for all $ (i,j) $ . The states of the other layers do not matter. Initially, all layers are transparent, that is, $ c(k,i,j)=0 $ for all $ k,i,j $ . Complete the target image by repeating the following operations at most $ N^2 $ times. - $ \mathrm{paint}(k,i,j,x) $ : Specify a layer $ k\in\{0,\cdots,K-1\} $ , a pixel $ (i,j) $ , and a color $ x\in\{0,\cdots,C\} $ , and change $ c(k,i,j) $ to $ x $ . **If $ x=0 $ is specified, that pixel becomes transparent again.** - $ \mathrm{copy}(k,h,r,\Delta i,\Delta j) $ : Specify layers $ k,h\in\{0,\cdots,K-1\} $ , an integer $ r\in\{0,\cdots,3\} $ , $ \Delta i\in\{-N+1,\cdots,N-1\} $ , and $ \Delta j\in\{-N+1,\cdots,N-1\} $ . Let $ h' $ be the layer obtained by rotating layer $ h $ clockwise by 90 degrees exactly $ r $ times. Note that layer $ h $ itself is not modified. Place $ h' $ so that its top-left pixel corresponds to pixel $ (\Delta i,\Delta j) $ of layer $ k $ , and overlay it. Then, overwrite layer $ k $ with all non-transparent pixels of $ h' $ . That is, for all $ (i,j) $ such that $ c(h',i,j)\neq 0 $ , update $ c(k,\Delta i+i,\Delta j+j)=c(h',i,j) $ . If this operation would paint any pixel outside the bounds of layer $ k $ , the output is judged as WA. **It is allowed that $ k=h $ .** - $ \mathrm{clear}(k) $ : Make all pixels of layer $ k $ transparent.

The input is given from Standard Input in the following format. > $ N $ $ K $ $ C $ $ g_{0,0} $ $ \cdots $ $ g_{0,N-1} $ $ \vdots $ $ g_{N-1,0} $ $ \cdots $ $ g_{N-1,N-1} $ The input satisfies the following constraints. - The side length $ N $ of each layer is fixed to $ N=32 $ . - $ K $ is an integer between $ 2 $ and $ 5 $ , inclusive, representing the number of layers. - $ C $ is an integer between $ 2 $ and $ 4 $ , inclusive, representing the number of colors. - $ g_{i,j} $ is an integer between $ 0 $ and $ C $ , inclusive, representing the color of pixel $ (i,j) $ in the target image. - Not all colors $ 1,\cdots,C $ necessarily appear in the target image. - The number of non-transparent pixels in the target image is at least $ N^2/2 $ .

Print the operations you perform to Standard Output in the order they are executed, one per line, in the following format. - $ \mathrm{paint}(k,i,j,x) $ > $ 0 $ $ k $ $ i $ $ j $ $ x $ - $ \mathrm{copy}(k,h,r,\Delta i,\Delta j) $ > $ 1 $ $ k $ $ h $ $ r $ $ \Delta i $ $ \Delta j $ - $ \mathrm{clear}(k) $ > $ 2 $ $ k $

### Scoring Let $ T $ be the number of operations. Let $ U $ be the number of non-transparent pixels in the target image, that is, the number of $ (i,j) $ satisfying $ g_{i,j}\neq 0 $ . Then, the score is calculated as follows: \\\[ \\mathrm{round}\\left(10^6\\times \\left(1+\\log\_2 \\frac{U}{T}\\right)\\right) \\\] The problem is divided into two subproblems: A and B, based on different input generation methods. Each subproblem contains 150 test cases, and the total score for a submission to that subproblem is the sum of the scores from all test cases in it. If your submission produces an illegal output or exceeds the time limit for some test cases, the submission itself will be judged as WA or TLE , and the score of the submission will be zero. The final ranking is determined by the sum of the highest scores obtained for each subproblem, and there will be no system test after the contest. If more than one team gets the same score, they will be ranked in the same place regardless of the submission time. ### Input Generation Let $ \mathrm{rand}(L,U) $ be a function that generates an integer uniformly at random between $ L $ and $ U $ , inclusive. The non-transparent pixels of a layer are said to be connected if the set of all non-transparent pixels is connected under 4-neighbor adjacency. Inputs for Problem A are generated as follows. #### Generation of $ N $ , $ K $ , and $ C $ $ N $ is fixed to $ 32 $ . $ K=\mathrm{rand}(2,5) $ and $ C=\mathrm{rand}(2,4) $ . #### Generation of $ g $ First, generate $ K'=\mathrm{rand}(1,2K) $ . Prepare $ K' $ transparent layers, and let $ c(k,i,j) $ denote the color of pixel $ (i,j) $ on layer $ k $ . Set $ c(0,N/2,N/2)=1 $ . Also, generate a parameter $ p=\mathrm{rand}(2,5) $ . Repeat the following process. Terminate the process when, for the first time, the number of non-transparent pixels in the layer updated by some operation becomes at least $ N^2/2 $ , and let the image of that layer, that is, the color of each pixel, be $ g_{i,j} $ . In each iteration, perform a paint operation with probability $ p/10 $ , and a copy operation with probability $ 1-p/10 $ . **paint operation:** Choose a layer by $ k=\mathrm{rand}(0,K'-1) $ . If layer $ k $ is transparent, set $ (i,j)=(N/2,N/2) $ ; otherwise, generate $ (i,j)=(\mathrm{rand}(0,N-1),\mathrm{rand}(0,N-1)) $ . Let $ \mathrm{num}(x) $ be the number of pixels of color $ x $ over all layers. Choose one color uniformly at random from the colors $ x\in\{1,\cdots,C\} $ that minimize $ \mathrm{num}(x) $ . Tentatively update $ c(k,i,j)=x $ , and check whether the non-transparent pixels of layer $ k $ are connected. If they are not connected, discard this trial and retry from the generation of $ (i,j) $ . **copy operation:** Generate the destination layer $ k=\mathrm{rand}(0,K'-1) $ . Choose a layer $ h $ with non-transparent pixels uniformly at random. Generate the number of rotations $ r=\mathrm{rand}(0,3) $ . Let $ h' $ be the layer obtained by rotating layer $ h $ clockwise by 90 degrees exactly $ r $ times. Among the non-transparent pixels of $ h' $ , let the minimum and maximum $ i $ -coordinates be $ i_0 $ and $ i_1 $ , and the minimum and maximum $ j $ -coordinates be $ j_0 $ and $ j_1 $ . Generate the shift amount $ (\Delta i,\Delta j) $ by $ (\mathrm{rand}(-i_0,N-1-i_1),\mathrm{rand}(-j_0,N-1-j_1)) $ . Tentatively apply the operation $ \mathrm{copy}(k,h,r,\Delta i,\Delta j) $ , and check whether the non-transparent pixels of layer $ k $ are connected. If they are not connected, discard this trial and retry from the selection of layer $ h $ , keeping the choice of $ k $ unchanged. ### Regarding Problem B **For Problem B, each team may create their own inputs and overwrite the default ones by submitting them.** Refer to the page for Problem C for instructions on how to submit your inputs. Each team may submit four inputs. Among the four submitted inputs, one is randomly selected and made public to all teams, while the remaining three are used for judging. **The input publication and the start of judging are scheduled to take place approximately 2 hours and 20 minutes after the contest begins.** An announcement will be made to all participants once the system is ready. For any team that does not submit their own inputs, four inputs will be generated randomly according to the input generation procedure described earlier. Since each team knows the contents of the inputs they submitted, it is allowed to precompute the corresponding outputs and embed them into the solution program. Submissions to Problem C may be made as many times as desired. However, for each team, only the last submission made **within 120 minutes** from the start of the contest that receives AC will be used for judging. ### Tools (Input generator and score calculation) - [Local version](https://img.atcoder.jp/masters2026-final/aCVc95hT.zip): You need a compilation environment of [Rust language](https://www.rust-lang.org/). - [Pre-compiled binary for Windows](https://img.atcoder.jp/masters2026-final/aCVc95hT_windows.zip): If you are not familiar with the Rust language environment, please use this instead. Please be aware that sharing visualization results or discussing solutions/ideas outside of the team during the contest is prohibited.