#include<stdio.h>
int main()
{int n,i,j;float el;
scanf("%d", &n);
    float *a=new float[n];
    for(i=1;i<=n;i++)
        scanf("%f" ,&a[i]);
for(i=1;i<=n-1;i++)
for(j=i+1;j<=n;j++)
if(a[i]<=a[j])
{
    el=a[i];
    a[i]=a[j];
    a[j]=el;
}
if(n%2!=0)
printf("%.1f",(a[(n+1)/2]));
else
printf("%.1f" ,(a[n/2]+a[(n/2)+1])/2);
return 0;
}


OR GIVE ME SOME HINTS!!!!!THANK!!!!

Edited by author 21.03.2007 20:48

Edited by author 21.03.2007 20:49

Edited by author 21.03.2007 20:50

you have to use O(n*logn) sort procedure!
your solution is O(n^2)!
if you will write QuickSort it will be Memory Limit on #7

HOW I CAN GET AC? THANK!!!IS O(N*LOGN)HELP ME?

Edited by author 21.03.2007 21:10

Sorry!CAN YOU SAY HOW USE O(N*LOGN)?THANK!!!!!!!

you can use heap (priority_queue)
http://acm.timus.ru/forum/thread.aspx?space=1&num=1306&id=14659&upd=633067488254848750

SORRY!!!I DON'T UNDERSTAND:
At first push n/2+1 numbers then do this
1 read next number
2 push it to queue
3 pop biggest element
4 goto 1
At the end use 2 or 1 top elements for answer
WHAT DO YOU MEAN?

heap is a data structure wich allows extract(pop) biggest element in log(n)
push is also log

this algo is included in c++

SORRY!ONE MORE QUESTION:HOW MUST I INCLUDE IT(INCLUDE FAIL NAME?)?THANK YOU VERY MUCH!!!!!!!!!

only cool c++ coders know it :)

P.S.
maybe <queue>?

Edited by author 22.03.2007 02:59

For completness!!
There are many effective stupid solutions also.
For example we use array xx[1..N/2+Buf] where
Buf=10000 and N/Buf times put in end of array new portion
of data and make qsort.
Thus we have O(log(N)*N*N/Buf) but used less memory
than when queue used.

SORRY!!!!IF YOU CAN,PLEASE SEND TO MY E-MAIL:SERCHCH@MAIL.RU PART OF SORT O(N*LOGN)!!!!THERE IS MANY PROBLEMS TO SORT,BUT I KNOW ONLY 2 SORT WAYS!!!