type
  u=record
      k,a:longint;
    end;
var
  s:array[0..50000] of u;
  t:array[0..50000,0..3] of longint;
  o,o2:array[0..50000] of longint;
  i,k,n:longint;
procedure sort(l,r:longint);
var
  i,j,w:longint;
  x,y:u;
begin
  i:=l;
  j:=r;
  x:=s[(l+r) div 2];
  repeat
    while s[i].a<x.a do i:=i+1;
    while x.a<s[j].a do j:=j-1;
    if i<=j then
    begin
      y:=s[i];
      s[i]:=s[j];
      s[j]:=y;
      w:=o[i];
      o[i]:=o[j];
      o[j]:=w;
      i:=i+1;
      j:=j-1;
    end;
  until i>j;
  if l<j then sort(l,j);
  if i<r then sort(i,r);
end;
begin
  readln(n);
  for i:=1 to n do
    begin
      readln(s[i].k,s[i].a);
      o[i]:=i;
    end;
  sort(1,n);
  for i:=1 to n do o2[o[i]]:=i;
  fillchar(t,sizeof(t),0);
  for i:=1 to n do t[i,0]:=s[i].k;
  for i:=2 to n do
    begin
      k:=1;
      while true do
        begin
          if s[i].k<t[k,0] then
            begin
              if t[k,2]=0 then
                begin
                  t[k,2]:=i;
                  t[i,1]:=k;
                  break;
                end
                          else k:=t[k,2];
            end
                           else
            begin
              if t[k,3]=0 then
                begin
                  t[k,3]:=i;
                  t[i,1]:=k;
                  break;
                end
                          else k:=t[k,3];
            end;
        end;
    end;
  for i:=1 to n do writeln(o[t[o2[i],1]],' ',o[t[o2[i],2]],' ',o[t[o2[i],3]]);
end.

• 顶~ (1709) realmajia 2005-07-26 19:53:15
  • upup (0) frkstyc 2005-07-26 19:54:26
    • 您不是AC了吗？ (0) JiangLY 2005-07-26 20:03:13
      • 呵呵，终于把主id磨出来了 (0) frkstyc 2005-07-26 20:03:51
        • 吃饭，什么都吃完饭再说 (0) frkstyc 2005-07-26 20:06:33
        • FT……我是把主ID调出来看哪些题没AC，发现BBS里的回复，就顺手发了 (0) JiangLY 2005-07-26 20:16:08
      • 按key排序，在树的最右路经上找到合适的位置插入 (0) frkstyc 2005-07-26 20:36:30
        • key是什么？ (0) JiangLY 2005-07-26 20:40:30
          • 知道了 (0) JiangLY 2005-07-26 20:41:31
            • 我就是按KEY排的序 (0) JiangLY 2005-07-26 20:42:44
        • 什么叫“在树的最右路经上找到合适的位置插入”？ (0) JiangLY 2005-07-26 20:42:18
          • 就是从最右边的节点向上找一个合适aux的位置 (0) frkstyc 2005-07-26 20:43:06
          • 像avl那样有个左旋操作吧 (0) Bluebird 2005-07-26 20:47:29
            • 这个只有一个元素，还比较简单吧 (0) frkstyc 2005-07-26 20:49:43
              • 哦，谢谢，明天再来改，现在去做一会儿NOI的题 (0) JiangLY 2005-07-26 20:52:22