СРОЧНО!!! ОСТАЛОСЬ МАЛО ВРЕМЕНИ!!! 15 БАЛЛОВ!!! Нужно ускорить работу программы по...

Question

СРОЧНО!!! ОСТАЛОСЬ МАЛО ВРЕМЕНИ!!! 15 БАЛЛОВ!!! Нужно ускорить работу программы по нахождению количества различных элементов в массиве. Массив достигает до 100 000 элементов, а сами элементы до 2 000 000 000. Код написан снизу. Можно что-то добавить или изменить, можно вообще другой код написать. Даю 15 чистых баллов. Язык паскаль (Free Pascal Compiler 3.0.0). Надеюсь на вашу помощь!!!!


var
a, b: array [1..100000] of int64;
i, n, c, j: longint;
tratata, d: boolean;

begin
readln(n);
for i := 1 to n do
begin
read(a[i]);
if a[i] = 0 then tratata := true;
d := false;
for j := 1 to n do
if a[i] = b[j] then d := true;
if not d then begin
inc(c);
b[c] := a[i];
end;
end;
if tratata then writeln(c + 1)
else writeln(c);
end.

Answer 1

Из небольших ускорений можно предложить проверять до b[c], дальше всё равно ничего нет. Но всё равно алгоритм будет делать порядка n^2 операций, что при n = 10^5 достаточно много. Кстати, 2*10^9 еще помещается в longint, int64 не нужен.

Можно пойти другим путём. Отсортируем массив A[i] за n log n, а потом для того, чтобы определить уникальные элементы, достаточно одного прохода по массиву.
Я буду сортировать сортировкой слиянием, вы можете использовать любую другую достаточно быструю сортировку.

procedure merge(var a: array of longint; left1, right1, left2, right2: integer);
var
  temp: array of longint;
  i, j, k: integer;
 
begin
  setLength(temp, right1 - left1 + right2 - left2 + 2);
  i := left1;
  j := left2;
  k := 0;
  while (i <= right1) and (j <= right2) do<br>  begin
    if a[i] <= a[j] then<br>    begin
      temp[k] := a[i];
      inc(i);
    end else begin
      temp[k] := a[j];
      inc(j);
    end;
    inc(k);
  end;
  while i <= right1 do<br>  begin
    temp[k] := a[i];
    inc(k);
    inc(i);
  end;
  while j <= right2 do<br>  begin
    temp[k] := a[j];
    inc(k);
    inc(j);
  end;
  for i := left1 to right1 do
    a[i] := temp[i - left1];
  for j := left2 to right2 do
    a[j] := temp[j - left2 + right1 - left1 + 1];
end;
 
procedure mergeSort(var a: array of longint; left, right: integer);
var
  t: longint;
 
begin
  if right - left = 0 then exit;
  if right - left = 1 then
  begin
    if a[left] > a[right] then
    begin
      t := a[left];
      a[left] := a[right];
      a[right] := t;
    end;
    exit;
  end;
  mergeSort(a, left, (left + right) div 2);
  mergeSort(a, (left + right) div 2 +  1, right);
  merge(a, left, (left + right) div 2, (left + right) div 2 + 1, right);
end;
 
var
  a: array of longint;
  i, n, count: integer;
 
begin
  read(n);
  setLength(a, n);
  for i := 0 to n - 1 do
    read(a[i]);
  mergeSort(a, 0, n - 1);
  count := 1;
  for i := 1 to n - 1 do
    if a[i] <> a[i - 1] then
      inc(count);
  writeln(count);
end.