Solution of 10107 - What is the Median

Problem Description
source:https://uva.onlinejudge.org/external/101/10107.html

Median plays an important role in the world of statistics. By definition, it is a value which divides an array into two equal parts. In this problem you are to determine the current median of some long integers. Suppose, we have five numbers {1,3,6,2,7}. In this case, 3 is the median as it has exactly two numbers on its each side. {1,2} and {6,7}. If there are even number of values like {1,3,6,2,7,8}, only one value cannot split this array into equal two parts, so we consider the average of the middle values {3,6}. Thus, the median will be (3+6)/2 = 4.5. In this problem, you have to print only the integer part, not the fractional. As a result, according to this problem, the median will be 4 !

Input 

The input file consists of series of integers X (0 ≤ X < 2 ³¹) and total number of integers N is less than 10000. The numbers may have leading or trailing spaces. 

Output 

For each input print the current value of the median. 

Sample Input 

1 
3 
4
60 
70 
50 
2 

Sample Output 

1 
2 
3 
3 
4 
27 
4

Solution:

#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include<stdio.h>
#include<stdlib.h>

void InsertionSort();

using namespace std;

long int a[10005];
long int indx;
int main()
{
    long int n,i,position,median;
    indx=0;
    while(scanf("%ld",&n)==1)
    {
        if(n==0)
            break;
        median=0;
        indx=indx+1;
        a[indx]=n;
        InsertionSort();
        if(indx%2==0)
        {
            position=indx/2;
            median=(a[position]+a[position+1])/2;
        }
        else
        {
            position=(indx+1)/2;
            median=a[position];
        }
        printf("%ld\n",median);
    }
    return 0;
}

void InsertionSort()
{
    int k,ptr,temp,j;
    if(indx<2)
        return;
    for(k=2;k<=indx;k++)
    {
        temp=a[k];
        ptr=k-1;
        while(temp<a[ptr])
        {
            a[ptr+1]=a[ptr];
            ptr=ptr-1;
        }
        a[ptr+1]=temp;
    }
}