Advertisement
Guest User

Untitled

a guest
Nov 23rd, 2014
177
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Pascal 2.24 KB | None | 0 0
  1. const fi='baib.inp';
  2.       fo='baib.out';
  3.  
  4. var a,b,c,ans:array[1..1000000] of longint;
  5.     n,i,j,next:longint;
  6. procedure init;
  7. var i:longint;
  8. begin
  9.   assign(input,fi);reset(input);
  10.   readln(n);
  11.   for i:=1 to n do
  12.     begin
  13.       readln(a[i],b[i]);
  14.       c[i]:=b[i];
  15.     end;
  16.   close(input);
  17. end;
  18.  
  19. procedure qsort(l,r:longint);
  20. var tm,i,j,p:longint;
  21. begin
  22.     if l>=r then exit;
  23.     i:=l;
  24.     j:=r;
  25.     p:=c[(l+r) div 2];
  26.     while i<=j do
  27.       begin
  28.         while c[i]<p do inc(i);
  29.         while c[j]>p do dec(j);
  30.         if i<=j then
  31.            begin
  32.              tm:=c[i];
  33.              c[i]:=c[j];
  34.              c[j]:=tm;
  35.              inc(i);
  36.              dec(j);
  37.            end;
  38.       end;
  39.    qsort(i,r);qsort(l,j);
  40. end;
  41.  
  42.  
  43. function check(i:longint):boolean;
  44. var l,r,m:longint;
  45. begin
  46.   l:=1;
  47.   r:=n;
  48.   while l<=r do
  49.     begin
  50.       m:=(l+r) div 2;
  51.       if i<c[m] then r:=m-1;
  52.       if i>c[m] then l:=m+1;
  53.       if i=c[m] then exit(true);
  54.     end;
  55.  exit(false);
  56. end;
  57.  
  58. procedure solve;
  59. var i:longint;
  60. begin
  61.   for i:=1 to n do if not check(a[i]) then
  62.     begin
  63.       ans[1]:=a[i];
  64.       break;
  65.     end;
  66. end;
  67.  
  68. procedure qsort2(l,r:longint);
  69. var tm,i,j,p:longint;
  70. begin
  71.     if l>=r then exit;
  72.     i:=l;
  73.     j:=r;
  74.     p:=a[(l+r) div 2];
  75.     while i<=j do
  76.       begin
  77.         while a[i]<p do inc(i);
  78.         while a[j]>p do dec(j);
  79.         if i<=j then
  80.            begin
  81.              tm:=a[i];
  82.              a[i]:=a[j];
  83.              a[j]:=tm;
  84.              tm:=b[i];
  85.              b[i]:=b[j];
  86.              b[j]:=tm;
  87.              inc(i);
  88.              dec(j);
  89.            end;
  90.       end;
  91.    qsort2(i,r);qsort2(l,j);
  92. end;
  93.  
  94. function nhiphan(i:longint):longint;
  95. var l,r,m,cur:longint;
  96. begin
  97.   l:=1;
  98.   r:=n;
  99.   cur:=0;
  100.   while l<= r do
  101.     begin
  102.       m:=(l+r) div 2;
  103.       if a[m]>i then r:=m-1;
  104.       if a[m]<i then l:=m+1;
  105.       if a[m]=i then exit(b[m]);
  106.     end;
  107. end;
  108. begin
  109.   assign(output,fo);rewrite(output);
  110.   init;
  111.   qsort(1,n);
  112.   solve;
  113.   qsort2(1,n);
  114.   ans[2]:=b[1];
  115.   j:=3;
  116.   i:=1;
  117.   next:=b[1];
  118.   while next<>0 do
  119.     begin
  120.       next:=nhiphan(ans[i]);
  121.       ans[j]:=next;
  122.       inc(i);
  123.       inc(j);
  124.     end;
  125.   for i:=1 to j-2 do write(ans[i],' ');
  126.   close(output);
  127. end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement