ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1136. Parliament

WA11 ??
Posted by tester 3 Jan 2006 23:23
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.
Re: WA11 ??
Posted by snake 10 Jan 2006 10:59
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.
Re: WA11 ??
Posted by jedimastex 17 Jan 2006 16:02
The other realization of the same algo is AC.
But where is the mistake here?
Re: WA11 ??
Posted by hatred 27 Oct 2010 15:51
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