Pagini recente » Cod sursa (job #2021797) | Cod sursa (job #826072) | Cod sursa (job #2240736) | Cod sursa (job #267617) | Cod sursa (job #503412)
Cod sursa(job #503412)
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.