ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1306. Sequence Median

AC pascal 0.14s solution
Posted by esbybb 6 Jul 2015 01:42
program ideone;
const TH : integer = 200000; //you can set it less or greater to speed up
INF : Cardinal = 2147483647+2;

var in1, reg, i,j,inx,i1,i2, shift, max, greater:Cardinal;
    n:Cardinal;
    var a :array of Cardinal;

    procedure QSort ( first, last: Cardinal);
   var L, R, c, X: Cardinal;
   begin
      if first < last then
      begin
         X:= a[(first + last) div 2];
         L:= first;
         R:= last;
            while L <= R do
            begin
               while a[L] < X do
                  L:= L + 1;
               while a[R] > X do
                  R:= R - 1;
               if L <= R then
               begin
                  c:= a[L];
                  a[L]:= a[R];
                  a[R]:= c;
                  L:= L + 1;
                  R:= R - 1;
               end;
           end;
        QSort(first, R);
        QSort(L, last);
     end;
end;

begin
    Read(n);

    if (n=1) then
    begin
        Readln(in1);
        writeln(in1);
        halt;
    end;
    shift :=0;
    max := 0;
    if (n>TH) then
    begin
        shift := n-TH;
        n := TH;
    end;
    setLength(a, n+1);

    for i:=1 to n do
    begin
        Read(in1);
        a[i] := in1;
    end;

    Qsort(1,n);
    max := a[n];

    for i:=1 to shift do
    begin
        Read(in1);
        if (in1>max) then
        begin
            a[i] := INF;
            greater := greater + 1;
        end else
        a[i] := in1;
    end;
    Qsort(1,n);

    n := n+shift;
    if (n mod 2=1) then
    begin
        writeln(a[n div 2+1 - shift]);
    end else
    begin
        inx := a[n div 2- (shift)] mod 2;
        inx := inx + a[n div 2 +1- (shift)] mod 2;
        write(a[n div 2- (shift)] div 2  + (a[n div 2 +1 - (shift)] div 2));
        if (inx=1) then
        begin
            write('.5');
        end;
    end;

end.