[EC Final 2022] Aqre

Luogu

IDLGP9727

Time1000ms

Memory1024MB

DifficultyP6

2022Special JudgeO2优化构造ICPCEC Final

Given an $n \times m$ matrix, you need to fill it with $0$ and $1$, such that: - There cannot be **four** consecutive horizontal or vertical cells filled with the same number. - The cells filled with $1$ form a connected area. (Two cells are adjacent if they share an edge. A group of cells is said to be connected if for every pair of cells it is possible to find a path connecting the two cells which lies completely within the group, and which only travels from one cell to an adjacent cell in each step.) Please construct a matrix satisfying the conditions above and has as many $1$s as possible. Output the maximum number of $1$s, and the matrix. ## Input The first line contains an integer $T~(1\leq T\leq 10^3)$ -- the number of test cases. For each test case, the first line contains two integers $n, m~(2\leq n, m\leq 10^3)$. ### It is guaranteed that the sum of $n\cdot m$ over all test cases does not exceed $10^6$. ## Output For each test case, output the maximum number of $1$s in the first line. Then output the matrix in the following $n$ lines. If there are multiple solution, output any. [samples]

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[EC Final 2022] Aqre",
    "description": {
      "content": "Given an $n \\times m$ matrix, you need to fill it with $0$ and $1$, such that: - There cannot be **four** consecutive horizontal or vertical cells filled with the same number. - The cells filled with",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9727"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given an $n \\times m$ matrix, you need to fill it with $0$ and $1$, such that:\n\n- There cannot be **four** consecutive horizontal or vertical cells filled with the same number.\n- The cells filled with...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments