시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 2 | 2 | 2 | 100.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.
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.
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)
N
is the number of monsters N.T
be the array returned by this function.T
should be N. If this condition is not satisfied, your program is judged as Wrong Answer [1].T
should be between 0 and N − 1, inclusive. If this condition is not satisfied, your program is judged as Wrong Answer [2].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)
a
and b
are the indices a, b of the monsters that will fight each other.true
. If the monster b wins, it returns false
.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).
Query
as “Accepted: 100
”.Wrong Answer [1]
”.If your program is judged as several types of Wrong Answer, the sample grader reports only one of them.
N ≤ 200.
The actual grader is not adaptive.
No additional constraints. In this subtask, if your program answers all the test cases correctly, your score is calculated as follows.
Query
among all test cases in this subtask.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)