DMOPC '20 Contest 7 P1 - Bob and Balance - DMOJ: Modern Online Judge

DMOPC '20 Contest 7 P1 - Bob and Balance

Points: 7 (partial)

Time limit: 2.0s

Python 4.0s

Memory limit: 256M

Python 512M

Author:

4fecta

Problem type

Bob is sitting through another session of physics class, with a topic regarding the force of gravity on an object. Bob thinks that the force of gravity is the same for all objects, regardless of their mass. However, his teacher Dr. Henri knows better. To convince Bob that he is wrong, Dr. Henri dug up $2N$ ~2N~ weights (the $i$ ~i~-th weight having mass $m_i$ ~m_i~ grams) and $N$ ~N~ balance scales (the traditional kind with plates to the left and right of the fulcrum).

Dr. Henri knows that the scales will tip to the plate holding a higher mass, or remain balanced if the masses on both sides are equal. To be as convincing as possible, Dr. Henri would like to arrange the $2N$ ~2N~ weights on the $N$ ~N~ scales with exactly one weight on each plate of each scale such that the maximum number of scales are tipped to either side. Please find an arrangement of the weights satisfying this requirement.

Constraints

$1 \le N \le 5 \times 10^5$ ~1 \le N \le 5 \times 10^5~

$1 \le m_i \le 10^9$ ~1 \le m_i \le 10^9~

Subtask 1 [20%]

$1 \le m_i \le 2$ ~1 \le m_i \le 2~

Subtask 2 [30%]

$1 \le N \le 2 \times 10^3$ ~1 \le N \le 2 \times 10^3~

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line contains an integer $N$ ~N~.

The second line contains $2N$ ~2N~ space-separated integers $m_i$ ~m_i~ $(1 \le i \le 2N)$ ~(1 \le i \le 2N)~, the masses of the weights.

Output Specification

On the first line output an integer $M$ ~M~, the maximum possible number of tipped scales.

On the $j$ ~j~-th of the next $N$ ~N~ lines, output $2$ ~2~ space-separated integers $a_j$ ~a_j~ and $b_j$ ~b_j~ $(1 \le a_j, b_j \le 2N)$ ~(1 \le a_j, b_j \le 2N)~, representing that the $j$ ~j~-th scale holds the $a_j$ ~a_j~-th weight on the left plate and the $b_j$ ~b_j~-th weight on the right plate.

Each weight must be placed on a plate, and one plate may only hold one weight. The number of tipped scales in your arrangement must be exactly $M$ ~M~. If there are multiple possible outputs satisfying these requirements, any of them will be accepted.

Sample Input

3
1 2 1 2 1 1

Sample Output

Explanation

The first scale will tip to the right, and the second scale will tip to the left. The third scale remains balanced. It can be proven that this is the maximum possible number of tipped scales, so this is a valid arrangement of the weights.

Comments

-1

glazed commented on Oct. 10, 2021, 1:39 p.m.

Why is my submission getting rte/tle?

1

andy_zhu23 commented on Oct. 10, 2021, 5:50 p.m. ← edit 2 →

your while loop will never end because i is not changing.

You should try compiling your code on your own computer first before submitting because your code cannot pass the sample

-1

glazed commented on Oct. 10, 2021, 10:16 p.m.

I fixed it but it's still not working. Can I see a solution? I'm a beginner so I have to learn implementation or maybe I am missing some knowledge.

0

d3story commented on Oct. 10, 2021, 10:52 p.m.

You are leaving out some corner cases try to make some test cases on your own. and there might be other things wrong that I don't see...