DMOPC '20 Contest 4 P2 - Beautiful Grids - Olympiads Online Judge

DMOPC '20 Contest 4 P2 - Beautiful Grids

Points: 7 (partial)

Time limit: 2.0s

Memory limit: 256M

Author:

Problem type

Penelope is playing a game on an $N \times M$ $N \times M$ grid! Her grid currently contains $K$ $K$ $1$ $1$ s, while the rest of her grid cells contain $0$ $0$ s.

Penelope isn't sure she likes her grid though. Specifically, she is worried that her grid isn't beautiful. A grid is beautiful if every row sum and column sum are even.

Penelope is in a hurry to make her grid beautiful so she asks you: how can she make her grid beautiful? On each move, you can flip the value of a grid cell: from $1$ $1$ to $0$ $0$ or $0$ $0$ to $1$ $1$ . Since she is in a hurry, she asks you to make her grid beautiful as fast as possible.

Constraints

$1 \le N, M \le 10^{18}$ $1 \leq N, M \leq 10^{18}$

$0 \le K \le \min(N \times M, 3 \times 10^5)$ $0 \leq K \leq min (N \times M, 3 \times 10^{5})$

$1 \le a_i \le N$ $1 \leq a_{i} \leq N$

$1 \le b_i \le M$ $1 \leq b_{i} \leq M$

All cells given are distinct.

Subtask 1 [30%]

$1 \le N, M \le 5000$ $1 \leq N, M \leq 5000$

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line contains $3$ $3$ integers, $N$ $N$ , the number of rows; $M$ $M$ , the number of columns; and $K$ $K$ .

The next $K$ $K$ lines each contain two integers $a_i$ $a_{i}$ and $b_i$ $b_{i}$ , indicating that the cell in the $a_i^\text{th}$ $a_{i}^{th}$ row, $b_i^\text{th}$ $b_{i}^{th}$ column contains a $1$ $1$ .

Output Specification

On the first line output $A$ $A$ , the minimum number of moves required to make the grid beautiful. $A$ $A$ must satisfy $0 \le A \le 10^6$ $0 \leq A \leq 10^{6}$ . It can be proven that the minimum $A$ $A$ lies within this range.

On the next $A$ $A$ lines, output two space-separated integers $a_i$ $a_{i}$ and $b_i$ $b_{i}$ , indicating that you will flip the cell in the $a_i^\text{th}$ $a_{i}^{th}$ row, $b_i^\text{th}$ $b_{i}^{th}$ column.

You may output any valid sequence.

Note: your output must follow the standard convention of not having any extra whitespace, and it must end with a new line.

Scoring

If you output an incorrect value $A$ $A$ , but a valid sequence of moves, you will receive $10\%$ $10 %$ for that test case.

If you output a correct value $A$ $A$ , but an invalid sequence of moves, you will receive $20\%$ $20 %$ for that test case.

If you output a correct value of $A$ $A$ and any valid sequence of moves, you will receive $100\%$ $100 %$ for that test case.

Your score for a subtask will be the minimum score across all test cases of that subtask.

Sample Input

Copy

Sample Output

Copy

1
2 3

Explanation

Note that after our operation, our grid is:

Copy

1 0 1
1 0 1

which satisfies the constraints.

Comments

-2

gavin_chen commented on Dec. 28, 2022, 8:33 p.m.

can someone tell me why im getting presentation error? there shoudlnt be aqny extra whitespace

0

andy_zhu23 commented on Dec. 28, 2022, 10:33 p.m.

I think for whatever value A you got, you didn't output A lines afterwards