17679번 - Minerals 서브태스크다국어언어 제한함수 구현

문제

Professor JOI’s laboratory is researching N kinds of minerals. There are 2 slices of each kind of mineral. There are 2N slices in total, numbered from 1 to 2N.

One day, as assistant Bitaro has dropped the box containing the 2N slices, he has no idea which slice and which slice are of the same kind of mineral.

The laboratory owns a device which can count the number of kinds of minerals when some slices are inserted in it, by measuring the wavelength each mineral absorbs. Bitaro is going to determine the N pairs of the same kind of mineral from the 2N slices. At first, there are no slices 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 Bitaro bringing 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.

구현

You need to submit one file.

The name of the file is minerals.cpp. It should implement the following function. The program should include minerals.h.

• void Solve(int N)
  This function is called exactly once for each test case.
  • The parameter N represents N, the number of kinds of minerals.

Your program can call the following functions.

• int Query(int x)
  For the index of the slice you specify, this function extracts the slice from the device if the slice is already in the device, or inserts the slice into the device otherwise. Then it returns the number of kinds of minerals in the device.
  • You specify the index x of the slice via parameter x. This must satisfy 1 ≤ x ≤ 2N. Otherwise, your program is considered as Wrong Answer [1].
  • The function Query must not be called more than 1 000 000 times. Otherwise, your program is considered as Wrong Answer [2].
• void Answer(int a, int b)
  Using this function, you answer the pairs of the same mineral.
  • The parameters a and b represent that the a-th slice and the b-th slice are the same kind of mineral. These must satisfy 1 ≤ a ≤ 2N and 1 ≤ b ≤ 2N. Otherwise, your program is considered as Wrong Answer [3]. If the same value appears more than once in a or b in total, your program is considered as Wrong Answer [4]. If slices of different kinds of mineral are specified, your program is considered as Wrong Answer [5].

The function Answer must be called exactly N times. If the number of calls to the function Answer is not N at the end of the execution of the function Solve, your program is considered as Wrong Answer [6].

입력

출력

제한

• 1 ≤ N ≤ 43 000.
• 1 ≤ X_i ≤ 2N (1 ≤ i ≤ N).
• 1 ≤ Y_i ≤ 2N (1 ≤ i ≤ N).
• X_i ≠ X_j (1 ≤ i < j ≤ N).
• Y_i ≠ Y_j (1 ≤ i < j ≤ N).
• X_i ≠ Y_j (1 ≤ i ≤ N, 1 ≤ j ≤ N).

X_i and Y_i (1 ≤ i ≤ N) denote that the X_i-th slice and the Y_i-th slice are the same kind of mineral.

예시

Here is a sample input for the sample grader and corresponding function calls.

4
1 5
2 6
3 4
7 8

서브태스크

힌트

첨부

• minerals-dist.zip