Cod sursa(job #503412)

Utilizator lianaliana tucar liana Data 22 noiembrie 2010 20:46:55
Problema Partitie Scor 60
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.81 kb
program partitie;
type element=record
  nr, poz:longint;
end;
var f, g:text;
    max, pmax, d, n, ng:longint;
    a, gr:array[0..300000] of longint;
    v:array[0..300000] of element;

procedure citire;
var i:longint;
  begin
    readln(f,n,d);
    for i:=1 to n do
      begin
        read(f,v[i].nr);
        v[i].poz:=i;
      end;
  end;

function pozitionare(i,j:longint):longint;
var x:element;
  begin
    x:=v[i];
    while i<j do
      begin
        while (j>i) and (x.nr<=v[j].nr) do
          j:=j-1;
        v[i]:=v[j];
        while (i<j) and (v[i].nr<=x.nr) do
          i:=i+1;
        v[j]:=v[i];
      end;
    v[i]:=x;
    pozitionare:=i;
  end;

procedure Qsort(st,dr:longint);
var m:longint;
  begin
    m:=pozitionare(st,dr);
    if st<m-1 then
      Qsort(st,m-1);
    if m+1<dr then
      Qsort(m+1,dr);
  end;

procedure rezolvare;
var i, j:longint;
  begin
    gr[v[1].poz]:=1;
    a[1]:=v[1].nr;
    ng:=1;
    for i:=2 to n do
      begin
        max:=-maxlongint;
        pmax:=-1;
        for j:=1 to ng do
          if v[i].nr-a[j]>=d then
            if a[j]>max then
              begin
                max:=a[j];
                pmax:=j;
              end;
        if max<>-maxlongint then
          begin
            a[pmax]:=v[i].nr;
            gr[v[i].poz]:=pmax;
          end
         else
           begin
             ng:=ng+1;
             a[ng]:=v[i].nr;
             gr[v[i].poz]:=ng;
           end;
      end;
  end;

procedure afisare;
var i:longint;
  begin
    writeln(g,ng);
    for i:=1 to n do
      writeln(g,gr[i]);
  end;

  begin
    assign(f,'partitie.in'); reset(f);
    assign(g,'partitie.out'); rewrite(g);
    citire;
    Qsort(1,n);
    rezolvare;
    afisare;
    close(f);
    close(g);
  end.