#P9326. [CCC 2023 S3] Palindromic Poster

    ID: 10438 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>模拟字符串2023Special JudgeCCC(加拿大)分类讨论

[CCC 2023 S3] Palindromic Poster

题目描述

Ryo and Kita are designing a new poster for Kessoku Band. After some furious brainstorming, they came to the conclusion that the poster should come in the form of a 2-D2\text{-D} grid of lowercase English letters (i.e. a to z), with NN rows and MM columns.

Furthermore, it is known that Ryo and Kita both have peculiar tastes in palindromes. Ryo will only be satisfied with the poster if exactly RR of its rows are palindromes, and Kita will only be satisfied with the poster if exactly CC of its columns are palindromes. Can you design a poster that will satisfy both Ryo and Kita, or determine that it is impossible to do so?

Note: A string is considered a palindrome if it is the same when read forwards and backwards. For example, kayak and bb are palindromes, whereas guitar and live are not.

输入格式

The first and only line of input consists of 44 space-separated integers N,M,RN, M, R, and CC.

The following table shows how the available 1515 marks are distributed.

Marks Bounds on NN Bounds on MM Bounds on RR Bounds on CC
22 marks 2N20002 \leq N \leq 2000 2M20002 \leq M \leq 2000 R=1R = 1 C=1C = 1
N=2N = 2 M=2M = 2 0RN0 \leq R \leq N 0CM0 \leq C \leq M
44 marks 2M20002 \leq M \leq 2000
77 marks 2N20002 \leq N \leq 2000

输出格式

If it is impossible to design a poster that will satisfy both Ryo and Kita, output IMPOSSIBLE on a single line.

Otherwise, your output should contain NN lines, each consisting of MM lowercase English letters, representing your poster design. If there are multiple possible designs, output any ofthem.

4 5 1 2
union
radar
badge
anime
2 2 2 1
IMPOSSIBLE

提示

Explanation of Output for Sample Input 11

In the given design, only the second row (namely radar) and the second and third columns (namely naan and iddi) are palindromes. Since exactly R=1R = 1 of the rows and C=2C = 2 of the columns are palindromes, this is an acceptable design.

Explanation of Output for Sample Input 22

In this case, it can be proven that it is impossible to satisfy both Ryo and Kita.

本题采用捆绑测试

  • Subtask 1(2 points):数据保证 2N20002 \leq N \leq 20002M20002\leq M\leq 2000R=1R = 1C=1C = 1

  • Subtask 2(2 points):数据保证 N=2N = 2M=2M = 20RN0\leq R\leq N0CM0\leq C\leq M

  • Subtask 3(4 points):数据保证 N=2N = 22M20002\leq M \leq20000RN0\leq R\leq N0CM0\leq C\leq M

  • Subtask 4(7 points):数据保证 2N20002\leq N\leq 20002M20002\leq M \leq20000RN0\leq R\leq N0CM0\leq C\leq M