Problem description
Managing a large crew isn't easy. It is your job, as a leader, to maintain statistical records of your subjects to guide your decision-making process. Upon entry into your team, individual team members take the Survival Ability Test (SAT) which measures their ability to contribute to your venture with an integer called the SAT Number. You would like to keep track of the average SAT Number of your team.
A convenient statistical indicator of average is the median, defined on Wikipedia as follows:
In statistics and probability theory, the median is the numerical value separating the higher half of a data sample, a population, or a probability distribution, from the lower half. The median of a finite list of numbers can be found by arranging all the observations from lowest value to highest value and picking the middle one (e.g., the median of {3, 3, 5, 9, 11} is 5). If there is an even number of observations, then there is no single middle value; the median is then usually defined to be the mean of the two middle values (the median of {3, 5, 7, 9} is (5 + 7) / 2 = 6), which corresponds to interpreting the median as the fully trimmed mid-range.
~ Wikipedia
It would have been easy to keep track of the median SAT Number if not for the fact that your crew is constantly changing. Just as quickly as you find new members for your crew, members are being lost to combat against literal Hellspawn. What's worse is that illness and superdrugs can change the SAT Number of existing crew as well.
Write a program to maintain a record of the median SAT Number of your crew given a series of events.
If the median is not an integer, you should return the greatest integer that is less than the median. In addition, all SAT numbers are guaranteed to be positive and to fit within a signed int.
Note: You will never need to find the median SAT Number of an empty crew.
This is a function call problem; you must not read from stdin or write to stdout. Instead, you are to download the attachment “middlenumber.cpp” and modify the function stubs in the file. You may also download “grader.cpp” to compile and debug your program. Please submit only your edited version of “middlenumber.cpp” to the judge!
Functions that you must implement
int init(int* arr, int length);
This function will be called once only, and before any other functions.
arr
is an array of integers of length
length
. The elements in
arr
are the SAT Numbers of your initial crew members. This function should return the initial median SAT Number.
int add_number(int x);
This function adds a member with SAT Number
x
to your crew. This function should return the new median SAT Number.
int remove_number(int x);
This function removes a member with SAT Number
x
from your crew. It is guaranteed that your crew is non-empty. This function should return the new median SAT Number.
int change_number(int old, int new);
This function changes the SAT Number of a crew member from
oldx
to
newx
. It is guaranteed that your crew contains at least one member with SAT Number
oldx
. This function should return the new median SAT Number.
Constraints
Let N be the number of function calls (including init).
Subtask 1 – 5 points: 1 ≤ N ≤ 100; there will be at most 100 initial crew members
Subtask 2 – 15 points: 1 ≤ N ≤ 1000; there will be at most 1000 initial crew members
Subtask 3 – 10 points: 1 ≤ N ≤ 100000; there will be at most 100000 initial crew members; there will be no calls to change and remove, and all calls to add will supply a SAT Number
x
that is larger than the SAT Number of any member in the crew at that time
Subtask 4 – 15 points: 1 ≤ N ≤ 100000; there will be at most 100000 initial crew members; there will be no calls to change and remove
Subtask 5 – 25 points: 1 ≤ N ≤ 100000; there will be at most 100000 initial crew members; the SAT Numbers of all crew members will be distinct
Subtask 6 – 30 points: 1 ≤ N ≤ 100000; there will be at most 100000 initial crew members
Subtask 7 – 0 points: sample
Sample input
init 5 1 3 5 3 6
change 3 9
remove 1
Sample output
3
5
5