middle.pas

Magio牛的usaco源代码

{
PROB:middle
LANG:PASCAL
}

program middle;
const
  maxn=9999;
var
  a:array[1..maxn]of longint;
  n,m,i:word;
procedure qsort(s,t:word);
  var
    p,i,j:word;
    ta:longint;
  begin
    if (s>=t) or (t<m) or (s>m) then exit;
    p:=s+random(t-s+1);
    ta:=a[p];a[p]:=a[s];
    i:=s;j:=t;
    repeat
      while (i<j) and (a[j]>=ta) do dec(j);
      if i=j then break;a[i]:=a[j];inc(i);
      while (i<j) and (a[i]<=ta) do inc(i);
      if i=j then break;a[j]:=a[i];dec(j);
    until i=j;
    a[i]:=ta;
    qsort(s,i-1);
    qsort(i+1,t);
  end;
begin
  assign(input,'middle.in');reset(input);
  assign(output,'middle.out');rewrite(output);
  read(n);m:=n shr 1+1;
  for i:=1 to n do
    read(a[i]);
  qsort(1,n);
  writeln(a[m]);
  close(input);close(output);
end.