Cod sursa(job #1214150)

Utilizator RusuAlexeiRusu Alexei RusuAlexei Data 29 iulie 2014 18:54:13
Problema Radix Sort Scor 30
Compilator fpc Status done
Runda Arhiva educationala Marime 1.64 kb
program radixsort;
  var bufout:array [1..100000] of byte;
      n,i,j:longint;
      x,y,z:int64;
      a:array[1..10000000] of int64;
      vis:array[1..10000000] of byte;
      count:array[0..99999] of longint;


begin
  assign(input,'radixsort.in');
  reset(input);
  assign(output,'radixsort.out');
  rewrite(output);
  settextbuf(output,bufout);

  readln(n,x,y,z);
  a[1]:=y;
  for i:=2 to n do
    begin
      a[i]:=(x*a[i-1]+y)mod z;

    end;
  for i:=1 to n do inc(count[a[i] mod 100000]);
  for i:=1 to 99999 do count[i]:=count[i]+count[i-1];

  for i:=n downto 1 do
    begin
      if vis[i]= 0 then
        begin
          y:=a[i];j:=i;
          repeat
            begin
              x:=y mod 100000;
              vis[j]:=1;
              j:=count[x];
              z:=y;
              y:=a[count[x]];
              a[count[x]]:=z;
              dec(count[x]);
            end;
          until vis[j]=1;
        end;
    end;
  for i:=0 to 99999 do count[i]:=0;
  for i:=1 to n do inc(count[a[i]div 100000]);
  for i:=1 to 99999 do count[i]:=count[i]+count[i-1];

  for i:=1 to n do vis[i]:=0;

  for i:=n downto 1 do
    begin
      if vis[i]= 0 then
        begin
          y:=a[i];j:=i;
          repeat
            begin
              x:=y div 100000;
              vis[j]:=1;
              j:=count[x];
              z:=y;
              y:=a[count[x]];
              a[count[x]]:=z;
              dec(count[x]);
            end;
          until vis[j]=1;
        end;
    end;

  i:=1;
  while i<=n do
    begin
      write(a[i],' ');
      i:=i+10;
    end;
  close(output);
end.