Paste Search Dynamic
MergeSort
  1. uses
  2.     sysutils, math;
  3.  
  4. const
  5.   maxn = 100000;
  6.   maxk = 10;
  7.   maxp = 300;
  8.   inf = 1e302;
  9.  
  10. type
  11.   int = longint;
  12.   real = extended;
  13.   tower = record
  14.     k : byte;
  15.     val : array[0..maxk] of byte;
  16.   end;
  17.  
  18. var
  19.   a : array[1..maxn] of tower;
  20.   id, tmp : array[1..maxn] of int;
  21.   px, py : array[0..maxk] of real;
  22.   n, p, u, v : int;
  23.  
  24. function Cmp(x, y : int) : boolean;
  25. var i, wx, wy : int;
  26.         rx, ry, tx, ty : real;
  27. begin
  28.         rx := 1;
  29.         ry := 1;
  30.         for i := 0 to maxk do
  31.         begin
  32.                 px[i] := inf;
  33.                 py[i] := inf;
  34.         end;
  35.         wx := 0;
  36.         wy := 0;
  37.         for i := maxk downto 0 do
  38.         begin
  39.                 tx := rx * log10(a[x].val[i]);
  40.                 if (tx > maxp) then
  41.                 begin
  42.                 wx := i;
  43.                 break;
  44.         end;
  45.                 rx := power(a[x].val[i], rx);
  46.                 px[i] := rx;
  47.         end;
  48.         for i := maxk downto 0 do
  49.         begin
  50.                 ty := ry * log10(a[y].val[i]);
  51.                 if (ty > maxp) then
  52.         begin
  53.                 wy := i;
  54.                         break;
  55.         end;
  56.                 ry := power(a[y].val[i], ry);
  57.                 py[i] := ry;
  58.         end;
  59.         if (px[0] <> py[0]) then
  60.         begin
  61.                 Cmp := boolean(px[0] < py[0]);
  62.                 exit;
  63.         end;
  64.         i := 0;
  65.         for i := 1 to maxk - 1 do
  66.         begin
  67.                 if ((px[i] < inf) and (py[i] < inf)) then
  68.                 begin
  69.                         if (i > 1) and (a[x].val[i - 2] <> 1) and (a[y].val[i - 2] <> 1) then
  70.                         begin
  71.                                 Cmp := boolean((px[i] * log10(a[x].val[i - 1]) + log10(log10(a[x].val[i - 2]))) <
  72.                                                         (py[i] * log10(a[y].val[i - 1]) + log10(log10(a[y].val[i - 2]))));
  73.                         end else
  74.                                 Cmp := boolean(px[i] * log10(a[x].val[i - 1]) < py[i] * log10(a[y].val[i - 1]));
  75.                         exit;
  76.                 end;
  77.         end;
  78.         Cmp := boolean(px[maxk - 1] * log10(a[x].val[maxk - 2]) <
  79.                                         py[maxk - 1] * log10(a[y].val[maxk - 2]));
  80. end;
  81.  
  82. procedure MergeSort(l, r : int);
  83. var i, j, k, m : int;
  84. begin
  85.         if l < r then
  86.         begin
  87.                 m := (l + r) div 2;
  88.                 MergeSort(l, m);
  89.                 MergeSort(m + 1, r);
  90.                 i := l;
  91.                 j := m + 1;
  92.                 for k := l to r do
  93.                 begin
  94.                         if (j > r) or (i <= m) and (Cmp(id[i], id[j])) then
  95.                         begin
  96.                                 tmp[k] := id[i];
  97.                                 inc(i);
  98.                         end else
  99.                         begin
  100.                                 tmp[k] := id[j];
  101.                                 inc(j);
  102.                         end;
  103.                 end;
  104.                 for k := l to r do
  105.                         id[k] := tmp[k];
  106.         end;
  107. end;
  108.  
  109. begin
  110.         read(n);
  111.         for u := 1 to n do
  112.         begin
  113.                 id[u] := u;
  114.                 read(a[u].k);
  115.                 p := a[u].k;
  116.                 for v := 0 to a[u].k do
  117.                 begin
  118.                         read(a[u].val[v]);
  119.                         if (a[u].val[v] = 1) and (v < p) then
  120.                                 p := v;
  121.                 end;
  122.                 a[u].k := p;
  123.                 for v := p + 1 to maxk do
  124.                         a[u].val[v] := 1;
  125.         end;
  126.         MergeSort(1, n);
  127.         for p := 1 to n do
  128.         begin
  129.                 if p > 1 then
  130.                         write(' ');
  131.                 write(id[p]);
  132.         end;
  133.         writeln;
  134. end.
Parsed in 0.029 seconds