Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on May 5th, 2012  |  syntax: Delphi  |  size: 3.94 KB  |  hits: 29  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. const n = 1000;
  2. type
  3. node = ^qqq;
  4. qqq = record
  5.   left, right : node;
  6.   key, prior : int64;
  7. end;
  8. decTree = object
  9.   private     head : node;
  10.   private     y : int64;
  11.   private     constructor aaa(var head : node);
  12.   private     procedure split(act : node; x : int64; var left, right : node);
  13.   private     procedure merge(var act : node; left, right : node);
  14.   private     procedure init(var act : node; x, prior : int64);
  15.   private     function  myExists(act : node; x : int64) : node;
  16.   private     procedure myDelete(var act : node; x : int64);
  17.   private     procedure myInsert(var act : node; it : node);
  18.   public      procedure insert(x : int64);
  19.   public      procedure delete(x : int64);
  20.   public      function exists(x : int64) : boolean;
  21. end;
  22.  
  23. constructor decTree.aaa(var head : node);
  24. begin
  25. head := nil;
  26. end;
  27.  
  28. procedure decTree.split(act : node; x : int64; var left, right : node);
  29. begin
  30.   if act = nil then
  31.   begin
  32.     left := nil;
  33.     right := nil;
  34.   end
  35.   else if (x < act.key) then
  36.   begin
  37.     split(act.left, x, left, act.left);
  38.     right := act;
  39.   end
  40.   else
  41.   begin
  42.     split(act.right, x, act.right, right);
  43.     left := act;
  44.   end;
  45. end;
  46.  
  47. procedure decTree.merge(var act : node; left, right : node);
  48. begin
  49.   if (left = nil) or (right = nil) then
  50.     if left = nil then
  51.       act := right else
  52.         act := left;
  53.   if (left <> nil) and (right <> nil) then
  54.   if (left.prior > right.prior) then
  55.   begin
  56.     merge(left.right, left.right, right);
  57.     act := left;
  58.   end
  59.   else
  60.   begin
  61.     merge(right.left, left, right.left);
  62.     act := right;
  63.   end;
  64. end;
  65.  
  66. procedure decTree.init(var act : node; x, prior : int64);
  67. begin
  68.   act.key := x;
  69.   act.prior := prior;
  70.   act.left := nil;
  71.   act.right := nil;
  72. end;
  73.  
  74. function decTree.myExists(act : node; x : int64) : node;
  75. begin
  76. if act <> nil then
  77. begin
  78.   if act.key < x then
  79.     if act.right <> nil then
  80.        myExists := myExists(act.right, x) else
  81.          myExists := nil;
  82.   if act.key > x then
  83.     if act.left <> nil then
  84.       myExists := myExists(act.left, x) else
  85.         myExists := nil;
  86.   if act.key = x then
  87.     myExists := act;
  88. end else
  89.   myExists := nil;
  90. end;
  91.  
  92. procedure decTree.myDelete(var act : node; x : int64);
  93. begin
  94.   if act.key = x then
  95.     merge(act, act.left, act.right) else
  96.     if x < act.key then
  97.       myDelete(act.left, x) else
  98.         myDelete(act.right, x);
  99. end;
  100.  
  101. procedure decTree.delete(x : int64);
  102. var act : node;
  103. begin
  104. new(act);
  105. if head <> nil then
  106.   begin
  107.     act := myExists(head, x);
  108.     if act <> nil then
  109.       myDelete(head, x);
  110.   end;
  111. end;
  112.  
  113. function decTree.exists(x : int64) : boolean;
  114. var act : node;
  115. begin
  116. exists := false;
  117. new(act);
  118. act := myExists(head, x);
  119. if act <> nil then
  120.   exists := true;
  121. end;
  122.  
  123. procedure decTree.myInsert(var act : node; it : node);
  124. begin
  125.   if act = nil then
  126.     act := it else
  127.   if (it.prior > act.prior) then
  128.   begin
  129.     split(act, it.key, it.left, it.right);
  130.     act := it;
  131.   end else
  132.   if it.key < act.key then
  133.     myInsert(act.left, it) else
  134.     if it.key > act.key then
  135.       myInsert(act.right, it);
  136. end;
  137.  
  138. procedure decTree.insert(x : int64);
  139. var act : node;
  140. begin
  141. new(act);
  142. y := 1;//random(1000000) + 0;
  143. init(act, x, y);
  144. myInsert(head, act);
  145. end;
  146.  
  147. var
  148.  
  149. a : array[0..n] of decTree;
  150. i, j : int64;
  151. f, t : text;
  152. c : char;
  153.  
  154. function h(s : int64) : int64;
  155. begin
  156. h := (s mod n);
  157. end;
  158.  
  159. begin
  160. assign(f, 'set.in');
  161. reset(f);
  162. assign(t, 'set.out');
  163. rewrite(t);
  164. while not eof(f) do
  165. begin
  166.   read(f, c);
  167.   if c = 'i' then
  168.   begin
  169.     read(f, c, c, c, c, c, c);
  170.     read(f, j);
  171.     a[h(j)].insert(j);
  172.   end else
  173.   if c = 'e' then
  174.   begin
  175.     read(f, c, c, c, c, c, c);
  176.     read(f, j);
  177.     if a[h(j)].exists(j) then
  178.       writeln(t, 'true') else
  179.         writeln(t, 'false');
  180.   end else
  181.   if c = 'd' then
  182.   begin
  183.     read(f, c, c, c, c, c, c);
  184.     read(f, j);
  185.     a[h(j)].delete(j);
  186.   end;
  187.   readln(f);
  188. end;
  189. close(f);
  190. close(t);
  191. end.
create a new version of this paste RAW Paste Data