[ICPC 2024 Xi'an I] Turn Off The Lights

Luogu

IDLGP10554

Time2000ms

Memory512MB

DifficultyP5

2024Special JudgeO2优化ICPC西安

Kitty has $n^2$ lights, which form an $n\times n$ matrix. One day, Kitty found that some of these lights were on, and some were off. Kitty wants to turn them all off. To achieve her goal, Kitty can perform three types of operations: - (1) Choose a row, reverse the state of this row. It means if a light of this row is on, after this operation, it is now off. If a light of this row is off, after this operation, it is now on. - (2) Choose a column, reverse the state of this column. It means if a light of this column is on, after this operation, it is now off. If a light of this column is off, after this operation, it is now on. - (3) Choose exactly one light, reverse the state of this light. **This operation can only be performed not more than $k$ times.** For the current state, help Kitty achieve her goal within $3n$ operations. ## Input The first line contains two integers $n(1\leq n\leq 1000),k(0\leq k < n)$, indicating as described above. Then $n$ lines follow, each line has exactly $n$ numbers, $0$ represents that the light is turned off at this time, while $1$ represents the opposite. The $y$-th number of the $(x+1)$-th line in input means the light at coordinate $(x,y)$. ## Output If Kitty can not achieve her goal,print $-1$ in a single line. Otherwise, print $M(0\leq M\leq 3n)$ in the first line, indicating the number of operations she needs to perform. The next $M$ lines, each line contains $2$ integers $x,y$, separated by white space. If $1\leq x\leq n,1\leq y\leq n$, it means Kitty will reverse the light at coordinate $(x,y)$. If $x=0,1\leq y\leq n$, it means Kitty will reverse all lights at coordinates $(z,y)1\leq z\leq n$. If $1\leq x\leq n,y=0$, it means Kitty will reverse all lights at coordinates $(x,z)1\leq z\leq n$. If there are multiple answers, print any of them. [samples]

Samples

Input #1

2 0
0 1
1 0

Output #1

2
0 2
2 0

Input #2

Output #2

-1

API Response (JSON)

{
  "problem": {
    "name": "[ICPC 2024 Xi'an I] Turn Off The Lights",
    "description": {
      "content": "Kitty has $n^2$ lights, which form an $n\\times n$ matrix. One day, Kitty found that some of these lights were on, and some were off. Kitty wants to turn them all off. To achieve her goal, Kitty can ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10554"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Kitty has $n^2$ lights, which form an $n\\times n$ matrix.\n\nOne day, Kitty found that some of these lights were on, and some were off. Kitty wants to turn them all off.\n\nTo achieve her goal, Kitty can ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments