시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB222100.000%

문제

A new video game is now on sale. In the world of this game, there are N monsters numbered from 0 to N −1. Each monster has an integer called its strength. The strength of the monster i (0 ≤ i ≤ N − 1) is Si. It is known that the strengths of the monsters satisfy the following conditions.

  • The strength of each monster is an integer between 0 and N − 1, inclusive.
  • No two different monsters have the same strength.

You can choose two monsters and make them fight each other. If the monster a and the monster b (0 ≤ a ≤ N − 1, 0 ≤ b ≤ N − 1, a , b) fight each other, the result of the fight is determined in the following way.

  • If |Sa − Sb| = 1, the monster with the smaller strength wins.
  • If |Sa − Sb| > 1, the monster with the larger strength wins.

Regardless of the result of the fight, you can make the same monster fight as many times as you want.

You do not know the strengths of the monsters in the beginning. You want to know the strength of every monster. For this purpose, you can make the monsters fight at most 25 000 times, and you know the results of the fights. Moreover, you want to minimize the number of fights.

Write a program which, given the number of the monsters, calculates the strength of every monster by making the monsters fight each other several times.

구현

You need to submit one file.

The file is monster.cpp. It should implement the following function. The program should include monster.h using the preprocessing directive #include.

  • std::vector<int> Solve(int N)
    For each test case, this function is called exactly once.
    • The parameter N is the number of monsters N.
    • This function returns an array which describes the strength of every monster. In the following, let T be the array returned by this function.
    • The length of T should be N. If this condition is not satisfied, your program is judged as Wrong Answer [1].
    • Each element of T should be between 0 and N − 1, inclusive. If this condition is not satisfied, your program is judged as Wrong Answer [2].
    • For every i (0 ≤ i ≤ N − 1), the equality T[i] = Si should hold. If this condition is not satisfied, your program is judged as Wrong Answer [3].

Your program can call the following function.

  • bool Query(int a, int b)
    Using this function, you make the monsters fight each other.
    • The parameters a and b are the indices a, b of the monsters that will fight each other.
    • This function returns the result of the fight. If the monster a wins, it returns true. If the monster b wins, it returns false.
    • The inequalities 0 ≤ a ≤ N − 1 and 0 ≤ b ≤ N − 1 should hold. If this condition is not satisfied, your program is judged as Wrong Answer [4].
    • The condition a ≠ b should hold. If this condition is not satisfied, your program is judged as Wrong Answer [5].
    • The function Query should not be called more than 25 000 times. If it is called more than 25 000 times, your program is judged as Wrong Answer [6].

입력

The sample grader reads the following data from the standard input.

N
S0 · · · SN−1

출력

When the program terminates successfully, the sample grader writes the following information to the standard output (quotes for clarity).

  • If your program is judged as correct, it writes the number of calls to the function Query as “Accepted: 100”.
  • If your program is judged as incorrect, it writes its type as “Wrong Answer [1]”.

If your program is judged as several types of Wrong Answer, the sample grader reports only one of them.

제한

  • 4 ≤ N ≤ 1 000.
  • 0 ≤ Si ≤ N − 1 (0 ≤ i ≤ N − 1).
  • Si ≠ Sj (0 ≤ i < j ≤ N − 1).

서브태스크 1 (10점)

N ≤ 200.

서브태스크 2 (15점)

The actual grader is not adaptive.

서브태스크 3 (75점)

No additional constraints. In this subtask, if your program answers all the test cases correctly, your score is calculated as follows.

  • Let X be the maximum of the number of calls to the function Query among all test cases in this subtask.
  • Your score of this subtask is calculated as follows
    • If 10 000 < X ≤ 25 000, your score is ⌊75 × (25 000 − X)/15 000⌋ points.
    • If X ≤ 10 000, your score is 75 points.

예제

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

Sample Input 1 Sample Function Calls
Call Return Call Return
5
3 1 4 2 0
Solve(5)      
    Query(1, 0) false
    Query(4, 0) false
    Query(1, 3) true
  [3, 1, 4, 2, 0]    

제출할 수 있는 언어

C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 예제는 채점하지 않는다.