Median

Welcome Guys !!
Here I have posting a puzzle that I have encountered in a programming contest and I have made a successful submission :

The median of M numbers is defined as the middle number after sorting them in order if M is odd or the average number of the middle 2 numbers (again after sorting) if M is even. You have an empty number list at first. Then you can add or remove some number from the list. For each add or remove operation, output the median of numbers in the list.

Example :
For a set of m = 5 numbers, { 9, 2, 8, 4, 1 } the median is the third number in sorted set { 1, 2, 4, 8, 9 } which is 4. Similarly for set of m = 4, { 5, 2, 10, 4 }, the median is the average of second and the third element in the sorted set { 2, 4, 5, 10 } which is (4+5)/2 = 4.5  

Input:
The first line is an integer n indicates the number of operations. Each of the next n lines is either “a x” or “r x” which indicates the operation is add or remove.

Output:
For each operation: If the operation is add output the median after adding x in a single line. If the operation is remove and the number x is not in the list, output “Wrong!” in a single line. If the operation is remove and the number x is in the list, output the median after deleting x in a single line. (if the result is an integer DO NOT output decimal point. And if the result is a real number , DO NOT output trailing 0s.)

Note
When calculating median in even case if your output is 3.0 print only 3 and if it is 3.50 print only 3.5

Constraints:
0 < n <= 100,000
For each “a x” or “r x”, x will always be an integer which will fit in 32 bit signed integer.

Sample Input:

7  
r 1  
a 1  
a 2  
a 1  
r 1  
r 2  
r 1  

Sample Output:

Wrong!  
1  
1.5  
1  
1.5  
1  
Wrong!

Note: As evident from the last line of the input, if after remove operation the list becomes empty you have to print “Wrong!” ( quotes are for clarity ). 

SOLUTION :

#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
int x[1000000];
char operation[1000000];
int number[1000000],T;
int total_size=0;
int median;
bool isFound=true;
double median_list[1000000];
int median_counter=0;
int search_location(int num){
int loc;
int start=0;
int mid;
int end=total_size-1;
while(start<=end){
mid=(start+end)/2;
if(x[mid]==num)
return mid;
else  if(x[mid]>num){
end=mid-1;
}else{
start=mid+1;
}

}
return -1;
}

void remove_from(int num){
if(total_size==0){
}
else{
int loc=search_location(num);
//cout<<"Element found at location :"<<loc;
if(loc!=-1){
for(int i=loc;i<total_size-1;i++){
x[i]=x[i+1];
}
total_size-=1;
}else{
isFound=false;
}

}
}
void insert_into(int num) {

int i=total_size-1;
while(num<x[i] && i>=0){
x[i+1]=x[i];
i--;
}
x[i+1]=num;
    total_size+=1;
}
void find_median(){
double median;
if(total_size==0){
median=99999999999;
}
else if(isFound==false){
median=99999999999;
isFound=true;
}
else if(total_size%2==0){
median=((double)x[total_size/2]+(double)x[(total_size/2)-1])/2;
//cout<<"The median is : "<<median;
}else{
median=(double)x[total_size/2];
///cout<<"The median is : "<<median;
}
median_list[median_counter]=median;
median_counter+=1;
}
int main(void){
cin>>T;
for(int i=0;i<T;i++){
cin>>operation[i]>>number[i];
}
for(int i=0;i<T;i++){

if(operation[i]=='a'){
insert_into(number[i]);
find_median();
}else if(operation[i]=='r'){
remove_from(number[i]);
find_median();
}
}

    for(int i=0;i<median_counter;i++){
    if(median_list[i]==99999999999){
    cout<<"Wrong!"<<"\n";
    }else{
    if(median_list[i]-(long long)median_list[i]!=0){
    printf("%0.1lf\n",median_list[i]);
    }else{
    printf("%lld\n",(long long)median_list[i]);
    }
    }
   
    }
   return 0;
}