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 \le N, M \le 10^{18}~

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

$1 \le a_i \le N$ ~1 \le a_i \le N~

$1 \le b_i \le M$ ~1 \le b_i \le M~

All cells given are distinct.

Subtask 1 [30%]

$1 \le N, M \le 5000$ ~1 \le N, M \le 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^\text{th}~ row, $b_i^\text{th}$ ~b_i^\text{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 \le A \le 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^\text{th}~ row, $b_i^\text{th}$ ~b_i^\text{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

Sample Output

1
2 3

Explanation

Note that after our operation, our grid is:

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