> 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.

• 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