Minerals
Time limit1sMemory limit256 MB
Given 2N slices forming N unknown pairs, determine all pairs using at most 1,000,000 device operations that report the number of distinct mineral kinds currently inserted.
- Level
Hard8 of 10
- Topics
- Divide and conquer, Implementation, Brute force, Math
- Solved
- No attempts yet
Problem
Professor JOI's laboratory is researching N kinds of minerals. There are 2 slices of each kind of mineral, so there are 2N slices in total, numbered from 1 to 2N.
One day, assistant Bitaro dropped the box containing the 2N slices, and now he has no idea which slice and which slice are of the same kind of mineral.
The laboratory owns a device which counts the number of kinds of minerals when some slices are inserted into it, by measuring the wavelength each mineral absorbs. Bitaro is going to determine the N pairs of the same kind of mineral among the 2N slices. At first, no slices are inserted in the device. Bitaro can perform the following operations:
- Inserting one slice into the device, Bitaro knows how many kinds of minerals are in the device.
- Extracting one slice from the device, Bitaro knows how many kinds of minerals are in the device.
So that Professor JOI will not find out that Bitaro brought about troubles, Bitaro can perform these operations at most 1 000 000 times in total.
Write a program which, given the number of kinds of minerals, using the device, determines all the pairs of the same kind of mineral.
Constraints
- 1 ≤ N ≤ 43 000.
- 1 ≤ Xi ≤ 2N (1 ≤ i ≤ N).
- 1 ≤ Yi ≤ 2N (1 ≤ i ≤ N).
- Xi ≠ Xj (1 ≤ i < j ≤ N).
- Yi ≠ Yj (1 ≤ i < j ≤ N).
- Xi ≠ Yj (1 ≤ i ≤ N, 1 ≤ j ≤ N).
Xi and Yi (1 ≤ i ≤ N) denote that the Xi-th slice and the Yi-th slice are the same kind of mineral.