Cod sursa(job #57118)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 1 mai 2007 11:04:22
Problema Oite Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.92 kb
var a:array[1..2000000] of longint;
    n,i,j,k,t,op,s,q,nr,nr2:longint;
    b,d,w:array[1..2000000] of int64;
    c:array[1..1024] of longint;
    f,g:text;
    ok:boolean;
procedure interclasez(st,mij,dr:longint);
 var i,j,k:longint;
 begin
  for i:=st to dr do begin
   b[i]:=a[i];
   w[i]:=d[i];
  end;
  i:=st; j:=mij+1; k:=st;
  while (i<=mij) and (j<=dr) do
   if b[i]>b[j] then begin
    a[k]:=b[i];
    d[k]:=w[i];
    inc(k);
    inc(i);
   end
   else begin
    a[k]:=b[j];
    d[k]:=w[j];
    inc(k);
    inc(j);
   end;
  for t:=i to mij do begin
   a[k]:=b[t];
   d[k]:=w[t];
   inc(k);
  end;
  for t:=j to dr do begin
   a[k]:=b[t];
   d[k]:=w[t];
   inc(k);
  end;
 end;
procedure mergesort(st,dr:longint);
 var mij:longint;
 begin
  if st<>dr then begin
   mij:=(st+dr) div 2;
   mergesort(st,mij);
   mergesort(mij+1,dr);
   interclasez(st,mij,dr);
  end;
 end;
function cauta(x,st,dr:longint):longint;
 var mij:longint;
 begin
  if st>dr then cauta:=0
  else
   begin
    mij:=(st+dr)div 2;
    if a[mij]=x then
     cauta:=mij
    else
     if a[mij]<x then
      cauta:=cauta(x,st,mij-1)
     else
      cauta:=cauta(x,mij+1,dr);
   end;
 end;
begin
 assign(f,'oite.in'); reset(f);
 assign(g,'oite.out'); rewrite(g);
 read(f,n,s);
 for i:=1 to n do
  read(f,c[i]);
 for i:=1 to n do
  for j:=i+1 to n do begin
    inc(op);
    a[op]:=c[i]+c[j];
    d[op]:=i*10000+j;
   end;
 mergesort(1,op);
 i:=1;
 ok:=false;
 nr:=0;
 for i:=1 to op do begin
  if a[i]<=op div 2 then
   break
  else begin
   q:=cauta(s-a[i],1,op);
   if q<>0 then
    inc(nr);
   while (q<n) and (a[q+1]=s-a[i]) do begin
    inc(q);
    inc(nr);
   end;
  end;
 end;
 if a[i]=s div 2 then
  q:=cauta(s div 2,1,op);
 while (q<>0) and (q<=n) and (a[q]=s div 2) do begin
  inc(nr2);
  inc(q);
 end;
 inc(nr,(nr2*(nr2-1)) div 2);
 writeln(g,nr);
 close(f); close(g);
end.