Cod sursa(job #125202)

Utilizator h_istvanHevele Istvan h_istvan Data 20 ianuarie 2008 12:01:49
Problema Partitie Scor 60
Compilator fpc Status done
Runda preONI 2008, Runda 3, Clasa a 9-a Marime 1.64 kb
program partitie;
var f:text;
    control:boolean;
    n,d,i,j,kn:longint;
    v:array[1..2,1..300000] of longint;
    h:array[1..300000] of longint;
    k:array[1..300000] of longint;

procedure qsort(bal,jobb:longint);
var i,j,va:longint;
    cs1,cs2:longint;
begin
     i:=bal;
     j:=jobb;
     va:=v[1,(i+j) div 2];
     while(i<=j) do
     begin
          while(v[1,i] < va) do inc(i);
          while(v[1,j] > va) do dec(j);
          if(i<=j) then
          begin
               cs1:=v[1,i];
               cs2:=v[2,i];
               v[1,i]:=v[1,j];
               v[2,i]:=v[2,j];
               v[1,j]:=cs1;
               v[2,j]:=cs2;
               inc(i);dec(j);
          end;
     end;
     if(bal<j) then qsort(bal,j);
     if(i<jobb) then qsort(i,jobb);
end;

begin
     assign(f,'partitie.in');
     reset(f);
     readln(f,n,d);
     for i:=1 to n do
     begin
          readln(f,v[1,i]);
          v[2,i]:=i;
     end;
     close(f);

     qsort(1,n);

     kn:=0;
     for i:=1 to n do
     begin
          control:=false;
          for j:=1 to kn do
          begin
               if(abs(v[1,i] - k[j]) >= d) then
               begin
                    h[v[2,i]]:=j;
                    k[j]:=v[1,i];
                    control:=true;
                    break;
               end;
          end;
          if not(control) then
          begin
               inc(kn);
               k[kn]:=v[1,i];
               h[v[2,i]]:=kn;
          end;
     end;

     assign(f,'partitie.out');
     rewrite(f);
     writeln(f,kn);
     for i:=1 to n do writeln(f,h[i]);
     close(f);
end.