DMOPC '20 Contest 7 P1 - Bob and Balance

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Python 4.0s
Memory limit: 256M
Python 512M

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 weights (the i-th weight having mass m_i grams) and 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 weights on the 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.


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

1 \le m_i \le 10^9

Subtask 1 [20%]

1 \le m_i \le 2

Subtask 2 [30%]

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

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line contains an integer N.

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

Output Specification

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

On the j-th of the next N lines, output 2 space-separated integers a_j and b_j (1 \le a_j, b_j \le 2N), representing that the j-th scale holds the a_j-th weight on the left plate and the 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. If there are multiple possible outputs satisfying these requirements, any of them will be accepted.

Sample Input

1 2 1 2 1 1

Sample Output

1 4
2 3
6 5


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.


  • 0
    glazed  commented on Oct. 10, 2021, 9:39 a.m.

    Why is my submission getting rte/tle?

    • 1
      andy_zhu23  commented on Oct. 10, 2021, 1: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, 6: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, 6: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...