oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

middlenumber Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

middlenumber.html

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

Tags

HCI NOI Selection Test 2014, Data Structure

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
15111s32MBMinimum
215111s32MBMinimum
310101s32MBMinimum
415101s32MBMinimum
525101s32MBMinimum
630101s32MBMinimum
7011s32MBMinimum

Attachments

Attachment Filesize Last Updated
grader.cpp1.54KB30 Jun 2018, 20:12:26
middlenumber.cpp252B30 Jun 2018, 20:12:26
middlenumber.h270B30 Jun 2018, 20:12:26

Judge Compile Command

g++-8 grader.cpp -o middlenumber -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.