18842번 - Chameleon’s Love 서브태스크다국어언어 제한함수 구현피드백

In JOI Zoo, there are 2N chameleons, numbered from 1 to 2N. Among them, N chameleons have sex X. The remaining N chameleons have sex Y.

Each chameleon has its original color. The following are known about the original colors.

• The original colors of the N chameleons of sex X are distinct.
• For each chameleon of sex X, there exists a unique chameleon of sex Y with the same original color.

Now, JOI Zoo is in the season of new loves.

• Each chameleon loves another chameleon. The following are known about the chameleons’ loves. • Each chameleon loves exactly one chameleon whose sex is different from itself.
• A chameleon and the chameleon which it loves have different original colors.
• There do not exist two chameleons which love the same chameleon.

You can gather some of the chameleons and organize a meeting. For each chameleon s attending the meeting, let t be the chameleon which s loves. The skin color of s is decided as follows.

• If t attends the meeting, the skin color of s is the original color of t.
• If t does not attend the meeting, the skin color of s is the original color of s.

The skin color of a chameleon may change for different meetings. For each meeting you organize, you can count the number of kinds of skin colors of the chameleons attending the meeting.

By organizing meetings at most 20 000 times, you want to determine all pairs of chameleons with the same original color.

Write a program which, given the number of chameleons, determines all pairs of chameleons with the same original color by organizing meetings at most 20 000 times.

You need to submit one file.

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

• void Solve(int N)
  This function is called exactly once for each test case.
  • The parameter N is N, the number of chameleons whose sexes are X.

Your program can call the following function.

• int Query(const std::vector &p)
  You organize a meeting of chameleons by calling this function.
  • The parameter p is the list of chameleons attending the meeting.
  • The return value is the number of kinds of skin colors of the chameleons attending the meeting.
  • Each element of the parameter p should be an integer greater between 1 and 2N, inclusive. If this condition is not satisfied, your program is judged as Wrong Answer [1].
  • The elements of the parameter p should be distinct. If this condition is not satisfied, your program is judged as Wrong Answer [2].
  • Your program should not call the function Query more than 20 000 times. If this condition is not satisfied, your program is judged as Wrong Answer [3].
• void Answer(int a, int b)
  By calling this function, you answer a pair of chameleons with the same original color.
  • The parameters a and b mean the chameleon a and the chameleon b have the same original color.
  • It must hold that 1 ≤ a ≤ 2N and 1 ≤ b ≤ 2N. If these conditions are not satisfied, your program is judged as Wrong Answer [4].
  • Your program should not call this function with same values of a or b more than once in total. If this condition is not satisfied, your program is judged as Wrong Answer [5].
  • If the original colors of the chameleon a and the chameleon b are different, your program is judged as Wrong Answer [6].
  • Your program should call the function Answer exactly N times. When the function Solve terminates, if the number of calls to the function Answer is different from N, your program is judged as Wrong Answer [7].

• 2 ≤ N ≤ 500.
• 0 ≤ Y_i ≤ 1 (1 ≤ i ≤ 2N).
• 1 ≤ C_i ≤ N (1 ≤ i ≤ 2N).
• For each j (1 ≤ j ≤ N), there exists a unique i (1 ≤ i ≤ 2N) satisfying Y_i = 0 and C_i = j.
• For each j (1 ≤ j ≤ N), there exists a unique i (1 ≤ i ≤ 2N) satisfying Y_i = 1 and C_i = j.
• 1 ≤ L_i ≤ 2N (1 ≤ i ≤ 2N).
• Y_i ≠ Y_Li (1 ≤ i ≤ 2N).
• C_i ≠ C_Li (1 ≤ i ≤ 2N).
• L_k ≠ L_l (1 ≤ k < l ≤ 2N).

Y_i (1 ≤ i ≤ 2N) is the sex of the chameleon i, which is 0 or 1. It is 0 if the sex is X, and 1 if the sex is Y.

C_i (1 ≤ i ≤ 2N) is the original color of the chameleon i, which is an integer greater than or equal to 1 and less than or equal to N.

L_i (1 ≤ i ≤ 2N) is the number of the chameleon which the chameleon i loves.

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

4
1 0 1 0 0 1 1 0
4 4 1 2 1 2 3 3
4 3 8 7 6 5 2 1

• chameleon-dist.zip