Here's my code. It gets WA11.
Algo: the rightmost number of the current subarray[i..j]
 is a root of a subtree. The left branch includes those and only those numbers which are less than root; right branch -
numbers greater than root. So if we swap these branches in our array and process them recursively we'll get the desired answer.

Example:
 1 7 5 (left br.)  21 22 27 25 20 (right br.) 10 (root)

1 (lb) 7 (rb) 5 (rt)
empty (lb) 21 22 27 25 (rb) 20 (rt)
21 22 (lb) 27 (rb) 25 (rt)
21 (lb) empty (rb) 22 (rt)

result:
 27 21 22 25 20 7 1 5 10

proc "tree" does all the work.
del is the delimiter of the branches.
I've used the most primitive algo to swap
the subarrays to simplify the solution.


program parliament;

{$APPTYPE CONSOLE}

var n,i:integer;
    a,t:array[1..100000] of integer;


procedure tree(i,j:integer);
var q,del:integer;
begin
 if j>=i then begin
  del:=j-1;
  while (del>=i) and (a[del]>a[j]) do dec(del);
   for q:=del+1 to j-1 do
    t[q+i-del-1]:=a[q];
   for q:=i to del do
    t[q+j-1-del]:=a[q];
   for q:=i to j-1 do a[q]:=t[q];
   tree(i,j-del-1); tree(j-del,j-1);
 end;
end;


begin

 fillchar(t,sizeof(t),0);
read(n);
 for i:=1 to n do read(a[i]);
 tree(1,n);
 for i:=1 to n do write(a[i],' ');
end.

So, I also have WA11!

What is wrong? I cant understand...

{$APPTYPE CONSOLE}
type Tchild=record
a,b:word;
end;

var
n,i:longint;
ar:array[1..4000] of word;
ch:array[1..4000] of Tchild;


procedure write0;
var child,oc:longint;
begin
child:=1;
oc:=1;
while (ch[child].a<>0)or(ch[child].b<>0) do begin
 oc:=child;
 if ch[child].b<>0 then child:=ch[child].b
 else child:=ch[child].a;
end;
if ch[oc].a=child then ch[oc].a:=0;
if ch[oc].b=child then ch[oc].b:=0;
write(ar[child],' ');
ar[child]:=0;
end;

procedure write1;
var child,oc:longint;
begin
child:=1;
oc:=1;
while (ch[child].a<>0)or(ch[child].b<>0) do begin
 oc:=child;
 if ch[child].a<>0 then child:=ch[child].a
 else child:=ch[child].b;
end;
if ch[oc].a=child then ch[oc].a:=0;
if ch[oc].b=child then ch[oc].b:=0;
write(ar[child],' ');
ar[child]:=0;
end;

procedure swap(var a,b:word);
var w:word;
begin
w:=a;
a:=b;
b:=w;
end;


procedure getplace(x,i:longint);
var old,p,child:longint;
begin
p:=1;
while true do begin
if (x>ar[p])and(ch[p].b=0) then begin
 ch[p].b:=i;
 exit;
end;
if (x<ar[p])and(ch[p].a=0) then begin
 ch[p].a:=i;
 exit;
end;

if (x>ar[p]) then begin
p:=ch[p].b;
continue;
end;

if (x<ar[p]) then begin
p:=ch[p].a;
continue;
end;
end;
end;

begin
fillchar(ch,sizeof(ch),0);
readln(n);
for i:=1 to n do read(ar[i]);
for i:=1 to n div 2 do swap(ar[i],ar[n-i+1]);


for i:=2 to n do getplace(ar[i],i);

if n mod 2=1 then begin
for i:=1 to n do write0;
end else begin
for i:=n downto 1 do write(ar[i],' ');
end;
end.

The other realization of the same algo is AC.
But where is the mistake here?

Why WA????????????????
#define clr(x,y) memset(x,y,sizeof(x))
using namespace std;

int a[400000];
int a1[400000],a2[400000];
int s[400000];
int n;

bool cmp(int x,int y)
{
    return a[x]<a[y];
}

int main(void)
{
    freopen("input.in","r",stdin);
    freopen("output.out","w",stdout);
    cin >>n;

    if (n<1)return 0;

    for (int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }

    int k1=0,k2=0;

    for (int i=0;i<n-1;i++)
    if (a[n-1]>a[i])
    {
        a1[k1++]=i;
    }
    else
    {
        a2[k2++]=i;
    }

    int t=-1;
    bool f=0;

    if (k2!=0)
    {
        sort(a2,a2+k2,cmp);

        for (int i=k2-2;i>=0;i--)
        {
//        cout << a[a2[i+1]]<< " " << a[a2[i]]<<endl;
            if (a2[i+1]<a2[i])
            {
                if (f)
                {
                    s[++t]=a2[i+1];
                    while (t>=0)cout << a[s[t--]]<< " ";
                }else
                cout << a[a2[i+1]]<< " ";
                f=0;
            }
            else
            {
                s[++t]=a2[i+1];
                f=1;
            }
        }

        s[++t]=a2[0];
        while (t>=0)cout << a[s[t--]]<< " ";
    }
    t=-1;
    f=0;

    if (k1!=0)
    {
        sort(a1,a1+k1,cmp);
        for (int i=k1-2;i>=0;i--)
        {
    //        cout << a[a2[i+1]]<< " " << a[a2[i]]<<endl;
            if (a1[i+1]<a1[i])
            {
                if (f)
                {
                    s[++t]=a1[i+1];
                    while (t>=0)cout << a[s[t--]]<< " ";
                }else
                cout << a[a1[i+1]]<< " ";
                f=0;
            }
            else
            {
                s[++t]=a1[i+1];
                f=1;
            }
        }

        s[++t]=a1[0];
        while (t>=0)cout << a[s[t--]]<< " ";
    }
    cout << a[n-1];


    return 0;
}

Edited by author 27.10.2010 15:51